对称二叉树

来自Leetcode第101题对称二叉树

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

---

递归

public boolean isSymmetric(TreeNode root) {
    return isMirror(root, root);
}

public boolean isMirror(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null) return true;
    if (t1 == null || t2 == null) return false;
    return (t1.val == t2.val)
            && isMirror(t1.right, t2.left)
            && isMirror(t1.left, t2.right);
}

迭代

来源题解

除了递归的方法外，我们也可以利用队列进行迭代。队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像。最初，队列中包含的是 root 以及 root。该算法的工作原理类似于 BFS，但存在一些关键差异。每次提取两个结点并比较它们的值。然后，将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。

业转载请联系作者获得授权，非商业转载请注明出处。

public boolean isSymmetric(TreeNode root) {
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    q.add(root);
    while (!q.isEmpty()) {
        TreeNode t1 = q.poll();
        TreeNode t2 = q.poll();
        if (t1 == null && t2 == null) continue;
        if (t1 == null || t2 == null) return false;
        if (t1.val != t2.val) return false;
        q.add(t1.left);
        q.add(t2.right);
        q.add(t1.right);
        q.add(t2.left);
    }
    return true;
}

栈

按自己思路写了一个，用栈的结构，效率低了好多。。

public boolean isSymmetric(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    stack.push(root);  //根结点两次入栈，方便后续比较
    while (!stack.isEmpty()) {
        TreeNode t1 = stack.pop();  //出栈
        TreeNode t2 = stack.pop();
        if (t1 == null && t2 == null) 
            continue;
        if (t1 == null || t2 == null) 
            return false;
        if (t1.val != t2.val) 
            return false;
        stack.push(t1.left);  //入栈
        stack.push(t2.right);
        stack.push(t1.right);
        stack.push(t2.left);
    }
    return true;
}