dfs-平衡二叉树-JZ39

最新推荐文章于 2025-03-16 17:49:02 发布

whl_program

最新推荐文章于 2025-03-16 17:49:02 发布

阅读量135

点赞数

分类专栏：剑指offer 文章标签：剑指offer dfs 回溯平衡二叉树 java

本文链接：https://blog.csdn.net/whl_program/article/details/119861048

版权

剑指offer 专栏收录该内容

67 篇文章

订阅专栏

描述
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

注：我们约定空树是平衡二叉树。
示例1

输入： {1,2,3,4,5,6,7}
返回值： true

思路：
通过递归和回溯可以处理这道题，考虑的思路为

对于父节点，需要确定两个子节点深度之差小于一。
对于作为子节点的立场，需要向自己的上一级节点传递的自己深度
空树深度为0，是平衡二叉树

时间复杂度：O(n) 其中 n 是所有节点个数
空间复杂度：O(n) 主要是递归方***占用本地方法栈，而递归层数不会超过n次

代码：

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if (depth(root) != -1) {
            return true;
        }
        return false;
    }
    private int depth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftLength = depth(root.left);
        int rightLength = depth(root.right);
        if (leftLength == -1 || rightLength == -1
            || leftLength - rightLength > 1 
            || rightLength - leftLength > 1) {
            //左右子树不满足高度差的要求 直接返回-1 减少判断次数
            return -1;
        }
        return 1 + max(leftLength, rightLength);
    } 
    private int max(int x, int y) {
        return x > y ? x : y;
    }
}