请概述网站建设的一般步骤,国际设计师网站有哪些,优秀个人网页设计图片,全屏网站 代码#xff08;一#xff09;问题描述
. - 力扣#xff08;LeetCode#xff09;. - 备战技术面试#xff1f;力扣提供海量技术面试资源#xff0c;帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/symmetric-tree/description/给你…一问题描述
. - 力扣LeetCode. - 备战技术面试力扣提供海量技术面试资源帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/symmetric-tree/description/给你一个二叉树的根节点 root 检查它是否轴对称。 示例 1 输入root [1,2,2,3,4,4,3]
输出true 示例 2 输入root [1,2,2,null,3,null,3]
输出false 提示
树中节点数目在范围 [1, 1000] 内-100 Node.val 100 进阶你可以运用递归和迭代两种方法解决这个问题吗
二解决思路 比较是否对称的思路可以转化成比较左子树内侧和右子树内侧是否相等、左子树外侧和右子树外侧是否相等如果相等说明二叉树对称。注意这里不是比较左孩子和右孩子是否相等。 1. 迭代法 这里迭代法可以用队列或者栈来完成。以队列为例左子树内侧和右子树内侧是否相等、左子树外侧和右子树外侧节点在队列中的位置应该是相邻的这样每次弹出两个元素进行比较如果一直比较到队列为空都没有出现不相等的情况那么就可以断定二叉树是对称的。不相等的情况有三种
左节点为空右节点不为空左节点不为空右节点为空左节点和右节点都不为空但是值不相等 如果左节点和右节点都为空但是队列还不为空那说明目前处理的节点是最底层的节点但比较并没有结束要将加入到队列里的节点都比较完。
/*** 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) {//这里实现队列要用LinkedList,不要用ArrayDeque//ArrayList不支持添加空元素QueueTreeNode qenew LinkedList();if(rootnull) return true;//比较的是左右子树不包括根节点//可以理解为后序遍历的思想把左右子树先加进来不用管最顶层的根节点qe.add(root.left);qe.add(root.right);while(!qe.isEmpty()){TreeNode leftNodeqe.poll();TreeNode rightNodeqe.poll();//两个节点都为空的情况if(leftNodenullrightNodenull){continue;}//三种不相等情况if(leftNodenull||rightNodenull||leftNode.val!rightNode.val){return false;}//注意添加的顺序要比较的两个节点放在一起//判断一下是否为空避免空指针的问题if(leftNode!null)qe.add(leftNode.left);if(rightNode!null)qe.add(rightNode.right);if(leftNode!null)qe.add(leftNode.right);if(rightNode!null)qe.add(rightNode.left);}return true;}
}
2. 递归法 写好递归法需要明确的三个部分
传入参数和返回值显然这里的参数是左节点和右节点返回值是判断的结果true和false处理逻辑在这个问题中是左节点和右节点相等时接下来需要再比较这两个节点下的两个子树的内侧和外侧是否分别相等终止条件在这个问题当中即传入的左右节点同时为空、左节点为空但右节点不为空、右节点不为空但左节点为空、左右节点的值不相等四种情况。其中左右节点同时为空说明遍历已经完成并且两侧子树层数相同在此之前都没有出现比较不相等的情况应当返回true。其他三种情况都是比较出现了不相等应当返回false。
/*** 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 symmetric(TreeNode left,TreeNode right){//终止条件if(left!nullrightnull) return false;if(leftnullright!null) return false;if(leftnullrightnull) return true;if(left.val!right.val) return false;//如果相等再比较它们子树的内外侧boolean outSidesymmetric(left.right,right.left);boolean inSidesymmetric(left.left,right.right);return outSideinSide;}public boolean isSymmetric(TreeNode root) {return symmetric(root.left,root.right);}
}
