101. 对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入： root = [1,2,2,3,4,4,3]
输出： true
示例 2：
输入： root = [1,2,2,null,3,null,3]
输出： false
提示：
- 树中节点数目在范围
[1, 1000]内 - − 100 ≤ N o d e . v a l ≤ 100 -100 \leq Node.val \leq 100 −100≤Node.val≤100
进阶： 你可以运用递归和迭代两种方法解决这个问题吗？
解法一(递归)
思路分析：
-
对于该题使用递归思路比较简单，即比较对称位置的两个节点是否相等
-
对于递归的参数，则传递需要比较的两个节点，同时返回值则返回比较结果，相等则继续返回
true，不相等则返回false -
对于递归的边界条件，需要注意的是，当对称位置两个节点均为
null时，也算相等，所以两个节点存在且只有一个节点为null时，显然直接返回false -
至于递归过程，则是判断当前 对称位置的两个节点是否相等，然后继续往下递归
实现代码如下：
class Solution {
public boolean isSymmetric(TreeNode root) {
// 注意题目条件 root != null
return doIsSymmetric(root.left, root.right);
}
private boolean doIsSymmetric(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;
// 相等比较 节点值 然后接着判断其余节点
return left.val == right.val && doIsSymmetric(left.left, right.right) && doIsSymmetric(left.right, right.left);
}
}
提交结果如下：
解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:40.4 MB,击败了13.09% 的Java用户
复杂度分析：
-
时间复杂度： O ( n ) O(n) O(n)，对二叉树的节点进行遍历
-
空间复杂度： O ( n ) O(n) O(n)，考虑递归对栈的消耗
解法二(迭代+栈)
思路分析：
-
根据递归，在计算机底层使用栈来实现，所以对于该题可以使用栈来进行迭代求解
-
因为题目给出二叉树至少有一个根节点，且对于根节点是否对称不需判断，因此可以使用两个栈，分别对二叉树的左右子树进行遍历。
-
根据对称，对二叉树的左子树采用中左右的顺序进行遍历，对于二叉树的右子树采用中右左的顺序进行遍历，然后判断是否对称。
实现代码如下：
class Solution {
public boolean isSymmetric(TreeNode root) {
// 注意题目条件 root != null
if (root.left == null && root .right != null)
return false; // 边界
if (root.left == null && root.right == null)
return true; // 边界特殊情况
if (root.left != null && root.right == null)
return false;
Deque<TreeNode> leftSt = new LinkedList<>(); // 对左子树按 中左右 进行遍历
Deque<TreeNode> rightSt = new LinkedList<>(); // 对右子树按 中右左 进行遍历
leftSt.push(root.left); // 左子树第一个节点进栈
rightSt.push(root.right); // 右子树第一个节点进栈
while (!leftSt.isEmpty() && !rightSt.isEmpty()) {
TreeNode left = leftSt.pop();
TreeNode right = rightSt.pop();
if (left == null && right == null)
continue;
if (left == null && right != null)
return false;
if (left != null && right == null)
return false;
if (left.val != right.val)
return false;
// 左子树 先进右节点 再进左节点
leftSt.push(left.right);
leftSt.push(left.left);
// 右子树 先进左节点 再进右节点
rightSt.push(right.left);
rightSt.push(right.right);
}
// 左右遍历栈 均为空 则说明对每个节点均完成对比
return leftSt.isEmpty() && rightSt.isEmpty();
}
}
提交结果如下：
解答成功:
执行耗时:1 ms,击败了18.71% 的Java用户
内存消耗:40.7 MB,击败了5.07% 的Java用户
复杂度分析：
-
时间复杂度： O ( n ) O(n) O(n)
-
空间复杂度： O ( n ) O(n) O(n)
总结：可进一步优化，使用一个双端队列，模拟两个栈
标签：null,LC,right,二叉树,&&,101,root,节点,left From： https://blog.csdn.net/qq_61457746/article/details/137107079