【Check 47】2024-04-09 - 101. 对称二叉树

[larscheng]

101. 对称二叉树

[larscheng]

思路

迭代

对称规律：left.left == right.right、left.right == right.left

迭代遍历，根据对称规律，将待比较的元素放进栈或者队列，依次比较

代码

    class Solution1 {

        public boolean isSymmetric(TreeNode root) {
            if (root == null || (root.left == null && root.right == null)) {
                return true;
            }
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root.left);
            stack.push(root.right);
            while (!stack.isEmpty()){
                TreeNode right = stack.pop();
                TreeNode left = stack.pop();
                if (right==null&&left==null){
                    continue;
                }
                if (right==null||left==null){
                    return false;
                }
                if (right.val!=left.val){
                    return false;
                }

                stack.push(left.left);
                stack.push(right.right);

                stack.push(left.right);
                stack.push(right.left);
            }
            return true;
        }
    }
}

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n)

[larscheng]

思路

递归检查 对称规律：left.left == right.right、left.right == right.left

递归检查左子树节点与右子树节点是否对称

代码

class Solution {

    public boolean isSymmetric(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) {
            return true;
        }
        return dfs(root.left,root.right);
    }

    private boolean dfs(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null) {
            //不匹配
            return false;
        }
        if (left.val != right.val) {
            //不匹配
            return false;
        }
        //递归检查子树
        return dfs(left.left,right.right)&&dfs(left.right,right.left);
    }
}

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n)