一道编程题——判断二叉树是否对称

题目描述

给定一棵二叉树，判断它是否是自身的镜像（即：二叉树是否为轴对称）

例如：下面这棵二叉树是对称的

而下面这棵二叉树不对称。

题目分析

看上图，很明显对二叉树的对称有了概念。

可以用递归或者迭代的方式：

递归：

如上图对称二叉树的第二行，根节点1的左子树2和右子树2的值相等，并且左子树2的左子树3和右子树2的右子树3相等。

所以递归公式为：checkout(root1.left, root2.right) and checkout(root1.right, root2.left)

即左子树的左子树应该等于右子树的右子树，并且左子树的右子树等于右子树的左子树。

递归过程实际上类似为左子树前序遍历（中、左、右），右子树反向前序遍历（中、右、左），然后判断这两个遍历过程是否相等。

python实现

# 递归
class Solution:
    def isSymmetric(self , root ):
        # write code here
        if not root:
            return True
        return self.checkout(root.left, root.right)
    
    def checkout(self, root1, root2):
        # 左右对应位置的节点都为空，对称
        if (not root1 and not root2):
            return True
        # 有一个节点为空，则不对称
        elif(not root1 or not root2):
            return False
        # 节点值不等，不对称
        elif(root1.val!=root2.val):
            return False
        # 继续递归
        else:
            return self.checkout(root1.left, root2.right) and self.checkout(root1.right, root2.left)

C++实现

// 递归
class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    bool isSymmetric(TreeNode* root) {
        // write code here
        if(!root){
            return true;
        }
        return check(root, root);
    }
    
    bool check(TreeNode* root1, TreeNode* root2){
        if(!root1 && !root2) return true;
        else if(!root1 || !root2) return false;
        else if(root1->val != root2->val) return false;
        return check(root1->left, root2->right) && check(root1->right, root2->left);
    }
};

迭代：

类似于BFS，逐层遍历节点入栈（或者队列），只不过入栈的顺序与层次遍历不太一样。

栈中元素为：[左子树，右子树] -> [左子树的左子树，右子树的右子树，左子树的右子树，右子树的左子树]

这样，只要比较栈中的成对的两个元素，直到栈为空。

python实现

# 迭代
class Solution2:
    def isSymmetric(self , root ):
        # write code here
        if (not root) or (not root.left and not root.right): 
            return True
        if not root.left or not root.right:
            return False
        stack = [root.left, root.right]
        while(stack):
            right_node = stack.pop()
            left_node = stack.pop()
            # 左右节点均为空
            if (not left_node and not right_node):
                continue
            # 左右节点均存在且相等，则继续加入到栈
            if (left_node and right_node) and (left_node.val == right_node.val):
                stack.extend([left_node.left, right_node.right, left_node.right, right_node.left])
            # 左右节点只有一个存在或者左右节点的值不等
            else:
                return False
        return True