二叉树的高度以及平衡

题目

https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof

解法

// 判断当前的树是不是平衡二叉树
思路是构造一个获取当前子树的深度的函数 depth(root) （即 面试题55 - I. 二叉树的深度 ），通过比较某子树的左右子树的深度差 abs(depth(root.left) - depth(root.right)) <= 1 是否成立，来判断某子树是否是二叉平衡树。若所有子树都平衡，则此树平衡。

public boolean isBalanced(TreeNode root) {
    if (root==null) return true;

    int leftTree = getHeight(root.left);
    int rightTree = getHeight(root.right);
    boolean res = Math.abs(leftTree-rightTree)<=1?true:false;
    if (res && isBalanced(root.left) && isBalanced(root.right)) {
        return true;
    } else {
        return false;
    }
}

private int getHeight(TreeNode node) {
    if (node == null) return 0;
    int left = getHeight(node.left);
    int right = getHeight(node.right);
    return Math.max(left, right) +1;
}

方法一：后序遍历 + 剪枝（从底至顶）
此方法为本题的最优解法，但剪枝的方法不易第一时间想到。

思路是对二叉树做后序遍历，从底至顶返回子树深度，若判定某子树不是平衡树则 “剪枝” ，直接向上返回。

// 判断左右子树 后序遍历
public boolean isBalanced2(TreeNode root) {
    return recur(root)  != -1;
}

// 后序遍历 计算左右子树高度差 >1 return -1;
private int recur(TreeNode root) {
    if (root == null) return 0;

    int left = recur(root.left);
    if (left == -1) return -1;

    int right = recur(root.right);
    if (right == -1) return -1;

    return Math.abs(left-right)<2?Math.max(left, right)+1 : -1;
}

2020-07-06

LC63_uniquePathsWithObstacles

二叉树的高度以及平衡

题目

解法

Links

Categorias

Nube de etiquetas

Recientes

Archivos

Etiquetas

Recientes

Archivos

Etiquetas

Your browser is out-of-date!