杭州网站建设哪家好,长沙网站建设公司哪家专业,wordpress yii,本地电脑做视频网站 外网连接不上目录题目分析递归法题目来源 101. 对称二叉树
题目分析
首先想清楚#xff0c;判断对称二叉树要比较的是哪两个节点#xff0c;要比较的可不是左右节点#xff01;
对于二叉树是否对称#xff0c;要比较的是根节点的左子树与右子树是不是相互翻转的#xff0c;理解这一…
目录题目分析递归法题目来源 101. 对称二叉树
题目分析
首先想清楚判断对称二叉树要比较的是哪两个节点要比较的可不是左右节点
对于二叉树是否对称要比较的是根节点的左子树与右子树是不是相互翻转的理解这一点就知道了其实我们要比较的是两个树这两个树是根节点的左右子树所以在递归遍历的过程中也是要同时遍历两棵树。
那么如何比较呢 比较的是两个子树的里侧和外侧的元素是否相等。如图所示 那么遍历的顺序应该是什么样的呢
本题遍历只能是“后序遍历”因为我们要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等。
正是因为要遍历两棵树而且要比较内侧和外侧节点所以准确的来说是左树的遍历顺序是左右中右树的遍历顺序是右左中。
递归法
递归三部曲
1.确定递归函数的参数和返回值 因为我们要比较的是根节点的两个子树是否是相互翻转的进而判断这个树是不是对称树所以要比较的是两个树参数自然也是左子树节点和右子树节点。
boolean compare(TreeNode left,TreeNode right)2.确定终止条件 要比较两个节点数值相不相同首先要把两个节点为空的情况弄清楚否则后面比较数值的时候就会操作空指针了。 节点为空的情况有注意我们比较的其实不是左孩子和右孩子所以如下我称之为左节点右节点 左节点为空右节点不为空不对称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;}3.确定单层递归的逻辑 此时才进入单层递归的逻辑单层递归的逻辑就是处理 左右节点都不为空且数值相同的情况。 比较二叉树外侧是否对称传入的是左节点的左孩子右节点的右孩子。比较内测是否对称传入左节点的右孩子右节点的左孩子。如果左右都对称就返回true 有一侧不对称就返回false 。 // 此时就是左右节点都不为空且数值相同的情况// 此时才做递归做下一层的判断boolean outside compare(left.left,right.right); // 左子树左、 右子树右boolean inside compare(left.right,right.left); // 左子树右、 右子树左// 左子树中、 右子树中 逻辑处理boolean result outside inside;代码实现
class Solution {public boolean isSymmetric(TreeNode root) {if(root null){return true;}return compare(root.left,root.right);}public static boolean compare(TreeNode left,TreeNode right){// 首先排除空节点的情况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;}// 此时就是左右节点都不为空且数值相同的情况// 此时才做递归做下一层的判断boolean outside compare(left.left,right.right); // 左子树左、 右子树右boolean inside compare(left.right,right.left); // 左子树右、 右子树左// 左子树中、 右子树中 逻辑处理boolean result outside inside;return result;}
}
