今日刷题重点—二叉树的对称性
226. 翻转二叉树
翻转一棵二叉树。
示例：
输入： 4 / \ 2 7 / \ / \ 1 3 6 9 输出： 4 / \ 7 2 / \ / \ 9 6 3 1
思路分析
反转二叉树:
本质就是:把每一个结点的左右孩子互换一下,除了叶子结点所有的都要进行这样的操作.
方法一:递归法(以先序为例)
递归三要素
递归参数:每次要交换的根节点(交换的是其左右节点)
结束条件:当root为null时.
确定单层递归的逻辑
因为是先前序遍历，所以先进行交换左右孩子节点，然后反转左子树，反转右子树。
参考代码1
//递归 TreeNode* invertTree(TreeNode* root) { if(root==NULL) { return NULL; } swap(root->left,root->right); invertTree(root->left); invertTree(root->right); return root; }
迭代法1(栈模拟)
用栈来模拟,因为递归的底层使用的就是栈.
参考代码2
//迭代法 TreeNode* invertTree(TreeNode* root) { if(root==NULL) { return NULL; } stack<TreeNode*> tab; tab.push(root); while(!tab.empty()) { TreeNode* node = tab.top();//中 tab.pop(); swap(node->left,node->right); if(node->left!=NULL) { //右 tab.push(node->left); } if(node->right!=NULL) { //左 tab.push(node->right); } } return root; }
迭代法2(队列模拟)
用层次遍历的思路也是可以的.
参考代码3
TreeNode* invertTree(TreeNode* root) { if(root==NULL) { return NULL; } queue<TreeNode*> Q; Q.push(root); while(!Q.empty()) { int size = Q.size(); for(int i = 0;i<size;i++){ TreeNode* node = Q.front(); Q.pop(); swap(node->left,node->right); if(node->left){ Q.push(node->left); } if(node->right){ Q.push(node->right); } } } return root; }
注意: 递归的中序遍历是不行的，因为使用递归的中序遍历，某些节点的左右孩子会翻转两次。
101. 对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。 1 / \ 2 2 / \ / \ 3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1 / \ 2 2 \ \ 3 3
思路分析
首先要清楚对称二叉树比较的是哪两个节点,要比较的可不是左右节点!
对于是否对称,要比较的是根节点的左右子树是否可以反转. 理解了这一点就知道,其实我们要比较的是两棵树,所以在递归遍历过程中要同时遍历这两棵树.
那么如何进行比较呢?
如下图,我们只需要外侧和外侧进行对比,内侧和内侧进行比较即可.
方法一:递归
递归三部曲:
- 确定参数和返回值:参数是左右子树,返回值是bool
- 确定终止条件
首先要把两个节点为空的情况弄清楚！ 否则后面比较数值的时候就会操作空指针了。
节点为空的情况有：
左节点为空，右节点不为空，不对称，return false
左不为空，右为空，不对称 return false
左右都为空，对称，返回true
左右节点不为空：
左右都不为空，比较节点数值，不相同就return false
剩下的一种情况就是,左右节点都不为空,而且其节点值相等.(我们后序在处理)
//先进行判空操作 if(!left&&right || left&&!right) { return false; } if(!left&&!right) { return true; } //在进行 根节点值不同的情况 if(left->val!=right->val) { return false; }
- 确定单层递归的逻辑
单层递归的逻辑就是处理 左右节点都不为空，且数值相同的情况。
- 比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
- 比较内测是否对称，传入左节点的右孩子，右节点的左孩子。
- 如果左右都对称就返回true ，有一侧不对称就返回false 。
//当前两个根节点的值相同,开始比较其树上的其他节点 bool outSide = isCompare(left->left,right->right); bool inSide = isCompare(left->right,right->left); return outSide&&inSide;
参考代码1
//递归.. bool isCompare(TreeNode* left,TreeNode* right) { //先进行判空操作 if(!left&&right || left&&!right) { return false; } if(!left&&!right) { return true; } //在进行 根节点值不同的情况 if(left->val!=right->val) { return false; } //当前两个根节点的值相同,开始比较其树上的其他节点 bool outSide = isCompare(left->left,right->right); bool inSide = isCompare(left->right,right->left); return outSide&&inSide; } bool isSymmetric(TreeNode* root) { if(root==NULL) { return true; } return isCompare(root->left,root->right); }
方法二: 迭代法(使用队列)
可以使用队列来判断左右节点及其子树是否对称.
参考代码2
bool isSymmetric(TreeNode* root) { if(root==NULL){ return true; } queue<TreeNode*> Q; Q.push(root->left); Q.push(root->right); while(!Q.empty()){ TreeNode* node1 = Q.front(); Q.pop(); TreeNode* node2 = Q.front(); Q.pop(); //进行判空操作 if(node1&&!node2 || !node1&&node2){ return false; } if(!node1&&!node2){//都为空说明是对称的,继续往下判断. continue; } if(node1->val!=node2->val){ return false; } //说明此刻当前俩节点值相等,继续判断其树上的节点是否相等. Q.push(node1->left); Q.push(node2->right); Q.push(node1->right); Q.push(node2->left); } return true; }
方法三:使用栈
方法二,其实是把左右两个子树要比较的元素顺序放进一个容器，然后成对成对的取出来进行比较，那么其实使用栈也是可以的。
参考代码3
bool isSymmetric(TreeNode* root) { if (root == NULL) return true; stack<TreeNode*> st; // 这里改成了栈 st.push(root->left); st.push(root->right); while (!st.empty()) { TreeNode* leftNode = st.top(); st.pop(); TreeNode* rightNode = st.top(); st.pop(); if (!leftNode && !rightNode) { continue; } if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) { return false; } st.push(leftNode->left); st.push(rightNode->right); st.push(leftNode->right); st.push(rightNode->left); } return true; }
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
思路分析
上题是对称,这个题是相等,只需要修改下比较的两个节点的顺序即可.
也有递归,迭代(通过队列),迭代(通过栈)
参考代码1
bool isSameTree(TreeNode* left, TreeNode* right) { //先进行判空操作 if(!left&&right || left&&!right) { return false; } if(!left&&!right) { return true; } //在进行 根节点值不同的情况 if(left->val!=right->val) { return false; } //当前两个根节点的值相同,开始比较其树上的其他节点 bool outSide = isSameTree(left->left,right->left); bool inSide = isSameTree(left->right,right->right); return outSide&&inSide; }
参考代码2
bool isSameTree(TreeNode* left, TreeNode* right) { //先进行判空操作 if(!left&&right || left&&!right) { return false; } if(!left&&!right) { return true; } //在进行 根节点值不同的情况 if(left->val!=right->val) { return false; } //当前两个根节点的值相同,开始比较其树上的其他节点 bool outSide = isSameTree(left->left,right->left); bool inSide = isSameTree(left->right,right->right); return outSide&&inSide; }
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
思路分析
这个题判断两个树是否是树A和子树B的关系.
只需要遍历A上的每一个子树,判断和B是否相等,如果相等,则返回true.当A上的所有结点遍历完了还没找到则说明不存在,返回false.
参考代码
bool isSameTree(TreeNode* left, TreeNode* right) { //先进行判空操作 if(!left&&right || left&&!right) { return false; } if(!left&&!right) { return true; } //在进行 根节点值不同的情况 if(left->val!=right->val) { return false; } //当前两个根节点的值相同,开始比较其树上的其他节点 bool outSide = isSameTree(left->left,right->left); bool inSide = isSameTree(left->right,right->right); return outSide&&inSide; } bool isSubtree(TreeNode* root, TreeNode* subRoot) { if(root==NULL){//我 root树都已经遍历完了还没找到则直接返回false return false; } //进行递归判断,只要有一个为真即为真. return isSameTree(root,subRoot)||isSameTree(root->left,subRoot) ||isSameTree(root->right,subRoot); }
