力扣101 对称二叉树 Java版本

---

题目描述

给你一个二叉树的根节点 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

进阶：你可以运用递归和迭代两种方法解决这个问题吗？

递归解法

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root==null){
            return true;
        }

        return judgeIsSymmetric(root.left,root.right);
    }

    public boolean judgeIsSymmetric(TreeNode leftChild,TreeNode rightChild){
        //这种情况是递归出口，当左右孩子都为空的时候就不需要向下判断了，直接返回true
        if (leftChild==null&&rightChild==null){
            return true;
        }
        //下面这三种情况都是不满足的时候，都需要返回false
        if(leftChild==null&&rightChild!=null){
            return false;
        }
        if (leftChild!=null&&rightChild==null){
            return false;
        }
        if (leftChild.val!= rightChild.val){
            return false;
        }
        //继续往下递归判断,判断左孩子的左孩子和右孩子的右孩子是否对称，判断左孩子的右孩子和右孩子的左孩子是否对称
        return judgeIsSymmetric(leftChild.left,rightChild.right)&&judgeIsSymmetric(leftChild.right,rightChild.left);


    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

非递归解法

思路在代码中详细注释了

class Solution {
    public boolean isSymmetric(TreeNode root) {
        //使用非递归的方式解决
        //利用栈来实现，有种消消乐的感觉，依次把对称的两个元素入栈，如果弹出的两个元素不相同则证明不是对称，相同则继续判断
        if (root == null) {
            return true;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root.left);
        stack.push(root.right);
        while (!stack.isEmpty()) {
            TreeNode rightChild = stack.pop();
            TreeNode leftChild = stack.pop();
            //如果左右孩子中有一个不是null但是另一个是null，则肯定不对称
            if ((leftChild == null && rightChild != null)||(leftChild!=null&&rightChild==null)) {
                return false;
            }
            if (leftChild != null && rightChild != null) {
                //值不相等也肯定不对称
                if (leftChild.val != rightChild.val) {
                    return false;
                }
                //其他情况就继续探索
                //再把对称的元素依次压入其中
                stack.push(leftChild.left);
                stack.push(rightChild.right);
                stack.push(leftChild.right);
                stack.push(rightChild.left);
            }
        }
        //都遍历完了之后则表明对称
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35