如何建设网站后台,以小说名字做网站的小说网,网站源码下载免费源码,哈密建设局网站摘要
101. 对称二叉树
一、对称二叉树解析
1.1 递归思路分析 首先想清楚#xff0c;判断对称二叉树要比较的是哪两个节点#xff0c;要比较的可不是左右节点#xff01;对于二叉树是否对称#xff0c;要比较的是根节点的左子树与右子树是不是相互翻转的#xff0c;理解…摘要
101. 对称二叉树
一、对称二叉树解析
1.1 递归思路分析 首先想清楚判断对称二叉树要比较的是哪两个节点要比较的可不是左右节点对于二叉树是否对称要比较的是根节点的左子树与右子树是不是相互翻转的理解这一点就知道了其实我们要比较的是两个树这两个树是根节点的左右子树所以在递归遍历的过程中也是要同时遍历两棵树。比较的是两个子树的里侧和外侧的元素是否相等。如图所示 那么遍历的顺序应该是什么样的呢本题遍历只能是“后序遍历”因为我们要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等。正是因为要遍历两棵树而且要比较内侧和外侧节点所以准确的来说是一个树的遍历顺序是左右中一个树的遍历顺序是右左中。
1.1.1 递归思路
确定递归函数的参数和返回值因为我们要比较的是根节点的两个子树是否是相互翻转的进而判断这个树是不是对称树所以要比较的是两个树参数自然也是左子树节点和右子树节点。返回值自然是bool类型。
bool compare(TreeNode* left, TreeNode* right)
确定终止条件要比较两个节点数值相不相同首先要把两个节点为空的情况弄清楚否则后面比较数值的时候就会操作空指针了。
节点为空的情况有注意我们比较的其实不是左孩子和右孩子所以如下我称之为左节点右节点
左节点为空右节点不为空不对称return false左不为空右为空不对称 return false左右都为空对称返回true
此时已经排除掉了节点为空的情况那么剩下的就是左右节点不为空
左右都不为空比较节点数值不相同就return false
此时左右节点不为空且数值也不相同的情况我们也处理了。
if (left NULL right ! NULL) return false;
else if (left ! NULL right NULL) return false;
else if (left NULL right NULL) return true;
else if (left-val ! right-val) return false; // 注意这里我没有使用else
注意上面最后一种情况我没有使用else而是else if 因为我们把以上情况都排除之后剩下的就是 左右节点都不为空且数值相同的情况。
确定单层递归的逻辑此时才进入单层递归的逻辑单层递归的逻辑就是处理 左右节点都不为空且数值相同的情况。
比较二叉树外侧是否对称传入的是左节点的左孩子右节点的右孩子。比较内侧是否对称传入左节点的右孩子右节点的左孩子。如果左右都对称就返回true 有一侧不对称就返回false 。
bool outside compare(left-left, right-right); // 左子树左、 右子树右
bool inside compare(left-right, right-left); // 左子树右、 右子树左
bool isSame outside inside; // 左子树中、 右子树中逻辑处理
return isSame;
如上代码中我们可以看出使用的遍历方式左子树左右中右子树右左中所以我把这个遍历顺序也称之为“后序遍历”尽管不是严格的后序遍历。
1.1.2 代码解析
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public boolean isSymmetric(TreeNode root) {if (rootnull){return true;}return isSymmetric2(root.left,root.right);}private boolean isSymmetric2(TreeNode left, TreeNode right) {if (leftnullrightnull){return true;}if (left!nullrightnull){return false;}if (leftnullright!null){return false;}if (left.val!right.val){return false;}boolean inisSymmetric2(left.right,right.left);boolean outisSymmetric2(left.left,right.right);return inout;}
}
1.1.3 复杂度分析
时间复杂度为O(N)空间复杂度为O(1) 利用一个数组来存储二叉树的中元素
1.2 层序遍历思路分析 二、对称二叉树类似问题
100. 相同的树
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if (pnullqnull){return true;}if (pnullq!null){return false;}if (p!nullqnull){return false;}if (p.val!q.val){return false;}return isSameTree(p.left,q.left)isSameTree(p.right,q.right);}
} 572. 另一棵树的子树
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(rootnull){return false;}return isSubtree2(root,subRoot)||isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot);}private boolean isSubtree2(TreeNode root1, TreeNode root2) {if (root1nullroot2null){return true;}if (root1nullroot2!null){return false;}if (root1!nullroot2null){return false;}if (root1.val!root2.val){return false;}return isSubtree2(root1.left,root2.left)isSubtree2(root1.right,root2.right);}
}
博文参考
《leetcode》