题解 | #对称的二叉树#

对称的二叉树

http://www.nowcoder.com/practice/ff05d44dfdb04e1d83bdbdab320efbcb

算法思想一：递归

解题思路：

对称二叉树定义：对于树中任意两个对称节点 L 和 R ，一定有：
    L.val = R.val：即此两对称节点值相等。
    L.left.val = R.right.val ：即 LL 的左子节点和 RR 的右子节点对称；
    L.right.val = R.left.val：即 LL 的右子节点和 RR 的左子节点对称。
根据以上规律，考虑从顶至底递归，判断每对节点是否对称，从而判断树是否为对称二叉树

算法流程：

isSymmetrical(root) ：
    特例处理：若根节点 root 为空，则直接返回 truetrue 。
    返回值：即 dfs(root.left, root.right) ;
dfs(L, R) ：
    终止条件：
        当 L 和 R 同时越过叶节点：此树从顶至底的节点都对称，因此返回 true ；
        当 L 或 R 中只有一个越过叶节点：此树不对称，因此返回 false ；
        当节点 L值 / 节点 R 值：此树不对称，因此返回 falsefalse ；
    递推工作：
        判断两节点 L.left 和 R.right 是否对称，即 dfs(L.left, R.right) ；
        判断两节点 L.right 和 R.left 是否对称，即 dfs(L.right, R.left) ；
    返回值：两对节点都对称时，才是对称树，因此用与逻辑符 && 连接

图解：

代码展示：

Python版本

class Solution:
    def isSymmetrical(self, pRoot):
        # write code here
        if not pRoot:
            return True
        def dfs(l, r):
            if not l and not r:
                return True
            if not l&nbs***bsp;not r:
                return False
            if l.val != r.val:
                return False
            # 递归左右子树
            return dfs(l.left, r.right) and dfs(l.right, r.left)
        return dfs(pRoot.left, pRoot.right)

复杂度分析：

时间复杂度O(N)：其中 N 为二叉树的节点数量，每次执行 dfs() 可以判断一对节点是否对称，因此最多调用 N/2次 dfs() 方法

空间复杂度O(N)：最差情况下，二叉树退化为链表，系统使用 O(N) 大小的栈空间

算法思想二：迭代

解题思路：

这道题目我们也可以使用迭代法，但要注意，这里的迭代法可不是前中后序的迭代写法，因为本题的本质是判断两个树是否是相互翻转的，其实已经不是所谓二叉树遍历的前中后序的关系了。
这里我们可以使用队列来比较两个树（根节点的左右子树）是否相互翻转，（注意这不是层序遍历）
通过队列来判断根节点的左子树和右子树的内侧和外侧是否相等，条件判断和递归的逻辑是一样的（队列为空跳出循环）

图解：

代码展示：

JAVA版本

public class Solution {
    boolean isSymmetrical(TreeNode pRoot)
    {
        if (pRoot == null){
            return true;
        }
        Queuedeque = new LinkedList<>();
        deque.offer(pRoot.left);
        deque.offer(pRoot.right);
        while (!deque.isEmpty()) {
            TreeNode leftNode = deque.poll();
            TreeNode rightNode = deque.poll();
            if (leftNode == null && rightNode == null) {
                continue;
            }
            // 以上三个判断条件合并
            if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
                return false;
            }
            // 这里顺序与使用Deque不同
            deque.offer(leftNode.left);
            deque.offer(rightNode.right);
            deque.offer(leftNode.right);
            deque.offer(rightNode.left);
        }
        return true;
    }
}