江苏省职业建设注册管理中心网站,网站内页seo,免费商城源码,最好的模板网站对称二叉树:Leecode 101
leecode 101 对称二叉树
根据题目描述#xff0c;首先想清楚#xff0c;对称二叉树要比较的是哪两个节点。对于二叉树是否对称#xff0c;要比较的是根节点的左子树与根节点的右子树是不是相互翻转的#xff0c;其实也就是比较两个树#xff0c;…对称二叉树:Leecode 101
leecode 101 对称二叉树
根据题目描述首先想清楚对称二叉树要比较的是哪两个节点。对于二叉树是否对称要比较的是根节点的左子树与根节点的右子树是不是相互翻转的其实也就是比较两个树即根节点的左右子树所以在遍历的过程中也要同时遍历两棵树。参考代码随想录
那要怎么比较呢比较的是两个子树的里侧和外侧元素是否相等。 使用递归法的三部曲
1.确定递归的参数和返回值
因为要比较的是根节点的左右子树是否相互翻转的进而判断是否对称二叉树所以要比较两个树参数即左子树节点和右子树节点返回值也就是boolean类型。
2.确定终止条件
根据上面的条件可以总结出终止条件分为以下几种情况: 节点为空的情况有 (1)判断根节点的左节点是否为空如果左右节点都为空那就是对称二叉树返回true (2)当其中一个节点为空另一个不为空则不是对称二叉树return false 此时已经排除掉了节点为空的情况那么剩下的就是左右节点不为空 (3)若左右节点不为空那么剩下的就是比较左右的数值情况 若左右节点不为空左子树的值不等于右子树的值也不是对称二叉树。return false 3.确定单层递归逻辑 单层递归逻辑就是处理左右节点都不为空且数值相同的情况 (1)比较二叉树外侧是否相等即传入左节点的左孩子和右节点的右孩子 (2)比较内测是否相等传入左节点的右孩子和右节点的左孩子。 (3)如果都相等返回TRUE 代码如下
public boolean isSymmetric1(TreeNode root) {return compare(root.left, root.right);}private boolean compare(TreeNode left, TreeNode right) {if (left null right ! null) {return false;}if (left ! null right null) {return false;}if (left null right null) {return true;}if (left.val ! right.val) {return false;}// 比较外侧boolean compareOutside compare(left.left, right.right);// 比较内侧boolean compareInside compare(left.right, right.left);return compareOutside compareInside;}
