【LeetCode】226.翻转二叉树
原题链接：🍏226. 翻转二叉树🍏
题目：给你一棵二叉树的根节点
root，翻转这棵二叉树，并返回其根节点。
思路：
我们把复杂问题简单化，先考虑交换左右孩子为：
root->left=right;//假设right为右孩子
root->right=left;//假设left为左孩子
如果利用递归的思想，这里right 和 left最好是翻转后的左右子树的根节点。
那么好了，left 和 right的值如何来？
我们就可以有这样的递归过程：
struct TreeNode* left=invertTree(root->left);
struct TreeNode* right=invertTree(root->right);
代码实现：
//方法1 struct TreeNode* invertTree(struct TreeNode* root) { if(root==NULL) { return NULL; } struct TreeNode* left=invertTree(root->left); struct TreeNode* right=invertTree(root->right); root->left=right; root->right=left; return root; } //方法2 struct TreeNode* invertTree(struct TreeNode* root) { if(root==NULL) { return NULL; } struct TreeNode* tmp=root->right; root->right=root->left; root->left=tmp; invertTree(root->left); invertTree(root->right); return root; }
【LeetCode】100.相同的树
原题链接：🍏100. 相同的树🍏
题目：给你两棵二叉树的根节点
p和q，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
思路：
以递归的思想思考
先递推到最基础的子问题：
最基础的单个节点是否相同，那么首先如果两个都为空，证明相同返回true；
如果有一个为空，另外一个不为空则不相同返回false；
如果两个节点的值不相同，则返回false；
最后回归到大问题：
如何证明两个树都相同呢？
我们可以从左子树开始依次判断，如果不同就直接返回false，只要过程中有一个函数返回false，那么会导致程序直接结束并返回false；
如果相同就继续判断右子树，如果左右子树都递推到空指针了，那么返回true。
代码实现：
bool isSameTree(struct TreeNode* p, struct TreeNode* q) { if(p == NULL && q == NULL) { return true; } //到达这里时，证明p、q至少有一个不为空 if(p == NULL || q == NULL)//那么如果再满足了当前判断的条件，就证明一个为空，一个不为空 { return false; } if(p->val!=q->val) { return false; } return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right); }
【LeetCode】5.对称二叉树
原题链接：🍏101. 对称二叉树🍏
题目：给你一个二叉树的根节点
root， 检查它是否轴对称。
思想：
大体思想其实与相同的子树相似， 只不过这次是一棵树，那么我们可以额外构建一个函数，传递两个指针参数（左右孩子指针），当作相同的子树那里的两棵树，并且比较时我们令两个指针的左孩子与右孩子比即可。
代码实现：
bool isSymmetricTree(struct TreeNode* p, struct TreeNode* q) { if(p == NULL && q == NULL) { return true; } if(p == NULL || q == NULL) { return false; } if(p->val!=q->val) { return false; } return isSymmetricTree(p->left,q->right)&&isSymmetricTree(p->right,q->left); } bool isSymmetric(struct TreeNode* root) { return isSymmetricTree(root->left,root->right); }
【LeetCode】9.另一颗树的子树
原题链接：🍏572. 另一棵树的子树🍏
题目：给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
思路：
根据题目，我们直到subRoot一定不为空，那么我们就需要判断root是否为空的情况，为空直接返回false即可。
什么时候开始进行判断是否为子树呢？
当root->val与subRoot->val相等时，就进入我们是否为子树的判断，这里的判断直接引用我们写的相同的子树即可。
函数返回值为bool值，我们可以采用下面的方式进行判断（逻辑与、逻辑或的结果是真/假）。
return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
显然中间的逻辑操作符采用 || ，因为左右子树中只要有一个是子树即可，左子树不符合还需要访问右子树，所以采用 || 。
代码实现：
bool isSameTree(struct TreeNode* p, struct TreeNode* q) { if(p == NULL && q == NULL) { return true; } if(p == NULL || q == NULL) { return false; } if(p->val!=q->val) { return false; } return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right); } bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) { if(root==NULL) { return false; } if(root->val==subRoot->val) { if(isSameTree(root,subRoot)) { return true; } } return isSubtree(root->left,subRoot) ||isSubtree(root->right,subRoot); }
