LC 101.对称二叉树

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\le Node.val\le 100$

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

解法一(递归)

思路分析：

1. 对于该题使用递归思路比较简单，即比较对称位置的两个节点是否相等

2. 对于递归的参数，则传递需要比较的两个节点，同时返回值则返回比较结果，相等则继续返回true，不相等则返回false

3. 对于递归的边界条件，需要注意的是，当对称位置两个节点均为null时，也算相等，所以两个节点存在且只有一个节点为null时，显然直接返回false

4. 至于递归过程，则是判断当前 对称位置的两个节点是否相等，然后继续往下递归

实现代码如下：

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)$，考虑递归对栈的消耗

解法二(迭代+栈)

思路分析：

1. 根据递归，在计算机底层使用栈来实现，所以对于该题可以使用栈来进行迭代求解

2. 因为题目给出二叉树至少有一个根节点，且对于根节点是否对称不需判断，因此可以使用两个栈，分别对二叉树的左右子树进行遍历。

3. 根据对称，对二叉树的左子树采用中左右的顺序进行遍历，对于二叉树的右子树采用中右左的顺序进行遍历，然后判断是否对称。

实现代码如下：

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)$

总结：可进一步优化，使用一个双端队列，模拟两个栈