[剑指 Offer 第 2 版第 28 题] “对称的二叉树”做题记录

第 28 题：对称的二叉树

传送门：对称的二叉树，牛客网 online judge 地址。

请实现一个函数，用来判断一棵二叉树是不是对称的。

如果一棵二叉树和它的镜像一样，那么它是对称的。

样例：

如下图所示二叉树 [1,2,2,3,4,4,3,null,null,null,null,null,null,null,null] 为对称二叉树： 1 / \ 2 2 / \ / \ 3 4 4 3 如下图所示二叉树 [1,2,2,null,4,4,3,null,null,null,null,null,null] 不是对称二叉树： 1 / \ 2 2 \ / \ 4 4 3

分析：LeetCode 上有类似的问题，使用双端队列可以完成，画图画到第 4 层就非常清晰了。

同 LeetCode 第 101 题。

解法1：递归写法。

Java 代码：

  class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }
    }

    public class Solution {
        boolean isSymmetrical(TreeNode pRoot) {
            if (pRoot == null) {
                return true;
            }
            return helper(pRoot.left, pRoot.right);
        }

        private boolean helper(TreeNode pRoot1, TreeNode pRoot2) {
            if (pRoot1 == null && pRoot2 == null) {
                return true;
            }
            if (pRoot1 == null || pRoot2 == null || pRoot1.val != pRoot2.val) {
                return false;
            }
            return helper(pRoot1.left, pRoot2.right) && helper(pRoot1.right, pRoot2.left);
        }
    }

Python 代码：

  # Definition for a binary tree node.
    class TreeNode(object):
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None


    # 递归写法：得引入辅助函数

    class Solution(object):
        def isSymmetric(self, root):
            """
            :type root: TreeNode
            :rtype: bool
            """
            # 先写递归终止条件
            if root is None:
                return True
            return self.__helper(root.left, root.right)

        def __helper(self, p1, p2):
            if p1 is None and p2 is None:
                return True
            if p1 is None or p2 is None:
                return False
            return p1.val == p2.val and self.__helper(p1.left, p2.right) and self.__helper(p1.right, p2.left)

解法2：非递归写法，借助双端队列辅助判断。自己画一个图，就好理解了。

Python 代码：

  # Definition for a binary tree node.
    class TreeNode(object):
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None


    # 非递归写法：借助双端队列辅助判断

    class Solution(object):
        def isSymmetric(self, root):
            """
            :type root: TreeNode
            :rtype: bool
            """
            # 先写递归终止条件
            if root is None:
                return True

            # 其实应该用 from collections import deque
            deque = []

            deque.insert(0, root.left)
            deque.append(root.right)

            while deque:
                l_node = deque.pop(0)
                r_node = deque.pop()

                # 这一步一定不要忘记了
                if l_node is None and r_node is None:
                    continue
                if l_node is None or r_node is None:
                    return False
                # 代码走到这里一定有 l_node 和 r_node 非空
                # 因此可以取出 val 进行判断了
                if l_node.val != r_node.val:
                    return False
                deque.insert(0, l_node.right)
                deque.insert(0, l_node.left)
                deque.append(r_node.left)
                deque.append(r_node.right)
            return True

“大雪菜”的写法：用栈模拟递归，对根结点的左子树，我们用中序遍历；对根结点的右子树，我们用反中序遍历。 则两个子树互为镜像，当且仅当同时遍历两棵子树时，对应结点的值相等。

时间复杂度：树中每个结点仅被遍历一遍，所以时间复杂度是 O(n)。

C++ 代码：

  /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        bool isSymmetric(TreeNode* root) {
            if (!root) return true;
            stack<TreeNode*> left, right;
            TreeNode *lc = root->left;
            TreeNode *rc = root->right;
            while(lc || rc || left.size())
            {
                while (lc && rc)
                {
                    left.push(lc), right.push(rc);
                    lc = lc->left, rc = rc->right;
                }
                if (lc || rc) return false;
                lc = left.top(), rc = right.top();
                left.pop(), right.pop();
                if (lc->val != rc->val) return false;
                // 这里反过来操作
                lc = lc->right, rc = rc->left;
            }
            return true;
        }

    };

作者：yxc 链接：https://www.acwing.com/solution/AcWing/content/747/ 来源：AcWing 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

作者：liweiwei1419

来源：https://liweiwei1419.github.io/sword-for-offer/