【LeetCode - 101】平衡二叉树

周三不加班

发布于 2019-09-03 10:21:55

3820

发布于 2019-09-03 10:21:55

文章被收录于专栏：程序猿杂货铺

题目

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

But the following [1,2,2,null,3,null,3] is not:

Note: Bonus points if you could solve it both recursively and iteratively.

翻译

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

说明:

如果你可以运用递归和迭代两种方法解决这个问题，会很加分。

解析

判断二叉树是否是平衡树，比如有两个节点n1, n2，我们需要比较n1的左子节点的值和n2的右子节点的值是否相等，同时还要比较n1的右子节点的值和n2的左子结点的值是否相等，以此类推比较完所有的左右两个节点。我们可以用递归和迭代两种方法来实现，写法不同，但是算法核心都一样。

对这棵树同时进行优先访问左子树的前序遍历和优先访问右子树的前序遍历，判断当前访问到的两个节点是不是相等。

然后遍历树的方式有：

可以采用DFS方式或BFS方式遍历树，并对比节点值
采用DFS方式时，对比根节点左右子树，交换其中一棵树的左右子树，对比对应的节点值
采用BFS方式时，从两侧遍历同一层节点，比对对应节点值

解法

递归解法

class Solution {
    public boolean isSymmetric(TreeNode root) {
        TreeNode p = root;
        TreeNode q = root;
        return helper(p, q);
    }

    private boolean helper(TreeNode p, TreeNode q) {
        // 判断有没有节点为null的情况，一句话搞定
        if (p == null || q == null) return p == q;
        return (p.val == q.val) && helper(p.left, q.right) && helper(p.right, q.left);
    }
}

迭代解法

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        Stack<TreeNode> pStack = new Stack<TreeNode>();
        Stack<TreeNode> qStack = new Stack<TreeNode>();
        TreeNode p = root;
        TreeNode q = root;
        while (p != null && q != null) {
            // 当前节点不相等，返回false
            if (!isEqual(p, q)) return false;
            if (p.right != null) pStack.push(p.right);
            if (q.left != null) qStack.push(q.left);
            p = p.left;
            q = q.right;
            if (p == null && q == null && !pStack.isEmpty() && !qStack.isEmpty()) {
                p = pStack.pop();
                q = qStack.pop();
            }
        }
        return p == q;
    }

    private boolean isEqual(TreeNode p, TreeNode q) {
        boolean children = true;
        if (p == null || q == null) return p == q;
        if (p.left == null || q.right == null) children = children && (p.left == q.right);
        if (p.right == null || q.left == null) children = children && (p.right == q.left);
        return (p.val == q.val) && children;
    }
}