1. 首页
  2. 剑指offer经典面试题

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

[剑指 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 层就非常清晰了。

liwei2019101110_1.png

同 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:非递归写法,借助双端队列辅助判断。自己画一个图,就好理解了。

liwei201910114_2.png

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/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

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

链接:https://www.javajike.com/article/3276.html

« [剑指 Offer 第 2 版第 27 题] “二叉树的镜像”做题记录
[剑指 Offer 第 2 版第 29 题] “顺时针打印矩阵”做题记录»

相关推荐

QR code