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

[剑指 Offer 第 2 版第 55_2 题] “平衡二叉树”做题记录

[剑指 Offer 第 2 版第 55_2 题] “平衡二叉树”做题记录

第 55-2 题:平衡二叉树

传送门:平衡二叉树牛客网 online judge 地址

输入一棵二叉树的根结点,判断该树是不是平衡二叉树。

如果某二叉树中任意结点的左右子树的深度相差不超过 1,那么它就是一棵平衡二叉树。

注意:

  • 规定空树也是一棵平衡二叉树。

样例:

输入:二叉树 [5,7,11,null,null,12,9,null,null,null,null] 如下所示, 5 / \ 7 11 / \ 12 9 输出:true

思路:深度优先遍历(后序遍历)。

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):
        # 全局变量
        flag = 1

        def isBalanced(self, root):
            """
            :type root: TreeNode
            :rtype: bool
            """

            if root is None:
                return True
            self.__dfs(root)
            return self.flag

        def __dfs(self, node):
            """
            返回以 root 为根的二叉树的高度,如果左右子树其中之一不是 AVL ,则返回 -1
            :param node:
            :return:
            """
            if node is None:
                return 0
            left = self.__dfs(node.left)
            right = self.__dfs(node.right)

            if abs(left - right) > 1:
                self.flag = 0
                # 这里不能写 return
            return max(left, right) + 1

Java 代码:

  class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    // 第 55 题:二叉树的深度(判断是不是平衡二叉树)
    // 可以提交到 LeetCode 第 110 题的测试用例
    // 参考资料1:
    // https://blog.csdn.net/derrantcm/article/details/46771529
    public class Solution {

        public boolean isBalanced(TreeNode root) {
            if (root == null) {
                return true;
            }
            int[] depth = new int[1];
            depth[0] = 0;
            return postOrder(root, depth);
        }

        // 后序遍历
        private boolean postOrder(TreeNode node, int[] depth) {
            if (node == null) {
                depth[0] = 0;
                return true;
            }
            int[] left = new int[1];
            int[] right = new int[1];
            // 如果左子树和右子树都不是平衡二叉树,直接就走到最后,返回 false
            if (postOrder(node.left, left) && postOrder(node.right, right)) {
                int diff = left[0] - right[0];
                if (diff <= 1 && diff >= -1) {
                    depth[0] = Integer.max(left[0], right[0]) + 1;
                    return true;
                }
            }
            return false;
        }
    }

作者:liweiwei1419

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


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

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

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

标题:[剑指 Offer 第 2 版第 55_2 题] “平衡二叉树”做题记录

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

« [剑指 Offer 第 2 版第 55-1 题] “二叉树的深度”做题记录
[剑指 Offer 第 2 版第 58-1 题] “翻转单词序列”做题记录»

相关推荐

QR code