数据结构与算法⑮(第四章_下)二叉树OJ(力扣:144,965,104,110,226,100,101,572)（上）：https://developer.aliyun.com/article/1513490
226. 翻转二叉树
难度简单
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
示例 2：
输入：root = [2,1,3]
输出：[2,3,1]
示例 3：
输入：root = []
输出：[]
提示：
- 树中节点数目范围在 [0, 100] 内
- -100 <= Node.val <= 100
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ struct TreeNode* invertTree(struct TreeNode* root){ }
解析代码（一）：
struct TreeNode* invertTree(struct TreeNode* root) { if (root == NULL) { return NULL; } //把左孩子和右孩子交换一下 struct TreeNode* tmp = root->left; root->left = root->right; root->right = tmp; //递归交换每一个结点和左孩子和右孩子 invertTree(root->left); invertTree(root->right); return root; }
解析代码（二）：
struct TreeNode* invertTree(struct TreeNode* root) { if (root == NULL) { return NULL; } //直接交换返回来的结点 struct TreeNode* rightTmp = root->right; root->right = invertTree(root->left); root->left = invertTree(rightTmp); return root; }
100. 相同的树
难度简单
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：
输入：p = [1,2,3], q = [1,2,3]
输出：true
示例 2：
输入：p = [1,2], q = [1,null,2]
输出：false
示例 3：
输入：p = [1,2,1], q = [1,1,2]
输出：false
提示：
- 两棵树上的节点数目都在范围 [0, 100] 内
- -10^4 <= Node.val <= 10^4
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ bool isSameTree(struct TreeNode* p, struct TreeNode* q){ }
解析代码：
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); }
101. 对称二叉树
难度简单
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
提示：
- 树中节点数目在范围 [1, 1000] 内
- -100 <= Node.val <= 100
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ bool isSymmetric(struct TreeNode* root){ }
解析代码：
bool _isSymmetric(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 _isSymmetric(p->left, q->right) && _isSymmetric(p->right, q->left); } bool isSymmetric(struct TreeNode* root){ if(root==NULL) { return true; } return _isSymmetric(root->left,root->right); }
572. 另一棵树的子树
难度简单
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
示例 1：
输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true
示例 2：
输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false
提示：
- root 树上的节点数量范围是 [1, 2000]
- subRoot 树上的节点数量范围是 [1, 1000]
- -10^4 <= root.val <= 10^4
- -10^4 <= subRoot.val <= 10^4
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ bool isSubtree(struct TreeNode* root, struct TreeNode* 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; } //遍历root的每一个结点和subRoot比较一下，一样就返回true if(isSameTree(root,subRoot)) { return true; } //遍历root的每一个结点,有一个true就是true return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot); }
