厦门城乡住房建设厅网站首页,厦门外贸建站,交互设计要学什么,网站建设公司推荐 知乎题目描述
给你一个二叉树的根节点 root #xff0c; 检查它是否轴对称。
题目示例 输入#xff1a;root [1,2,2,3,4,4,3] 输出#xff1a;true 解题思路
首先想清楚#xff0c;判断对称二叉树要比较的是哪两个节点#xff0c;要比较的可不是左右节点#xff01;
对于…题目描述
给你一个二叉树的根节点 root 检查它是否轴对称。
题目示例 输入root [1,2,2,3,4,4,3] 输出true 解题思路
首先想清楚判断对称二叉树要比较的是哪两个节点要比较的可不是左右节点
对于二叉树是否对称要比较的是根节点的左子树与右子树是不是相互翻转的理解这一点就知道了其实我们要比较的是两个树这两个树是根节点的左右子树所以在递归遍历的过程中也是要同时遍历两棵树。
比较的是两个子树的里侧和外侧的元素是否相等。
本题遍历只能是“后序遍历”因为我们要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等。
参考代码
class Solution {public boolean isSymmetric(TreeNode root) {// 采用后序遍历因为左右孩子需要给上层返回信息return compare(root.left, root.right);}public 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;}
}
