求解二叉树的最大深度和判断是否是平衡二叉树

算法

发布日期: 2019-08-28

阅读次数:

求解二叉树的最大深度

题目要求

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

返回它的最大深度 3 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/balanced-binary-tree

定义一个二叉树的结构如下所示

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
    }
}

####解决方案

这里我们直接使用递归的方法，深度优先遍历即可解决问题。

public class Solution {
    public int maxDepth(TreeNode root) {
        return height(root);
    }
    public int height(TreeNode root) {
        if (root == null) return 0;
        int left = height(root.left) + 1;
        int right = height(root.right) + 1;
        return Math.max(left, right);
    }
}

####复杂度分析

时间复杂度：我们每个结点只访问一次，因此时间复杂度为 O(N)O(N)，
其中 NN 是结点的数量。
空间复杂度：在最糟糕的情况下，树是完全不平衡的，例如每个结点只剩下左子结点，递归将会被调用 N 次（树的高度），因此保持调用栈的存储将是 O(N)。但在最好的情况下（树是完全平衡的），树的高度将是 log(N)。因此，在这种情况下的空间复杂度将是O(log(N))。

判断二叉树是否是平衡二叉树

题目要求

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

返回 false 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/balanced-binary-tree

解决方案

这道题目是在上一道题目上的一个延伸问题，并不难解决。

public class Solution {
    boolean res = true;
    public boolean isBalanced(TreeNode root) {
        helper(root);
        return res;
    }
    private int helper(TreeNode root) {
        if (root == null) return 0;
        int left = helper(root.left) + 1;
        int right = helper(root.right) + 1;
        if (Math.abs(right - left) > 1) res = false;
        return Math.max(left, right);
    }
}

只需要多判断一个left与right的绝对值的差值是否小于1，即可解决问题。