平衡二叉树

题目描述

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

示例

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

    3
   / \
  9  20
    /  \
   15   7
返回 true 。

思路

1. 可以使用递归算法求解。
2. 递归处理每个结点，首先计算当前结点左右子树的高度，判断高度差是否小于2；
   • 若小于2，则对其左右孩子结点继续递归操作
   • 若大于等于2，直接返回false即可。

Java代码实现

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

        int leftDepth = getTreeDepth(root.left);
        int rightDepth = getTreeDepth(root.right);

        if(Math.abs(leftDepth-rightDepth)>1){
            return false;
        }

        return isBalanced(root.left) && isBalanced(root.right);
    }

    private int getTreeDepth(TreeNode root){
        if(root == null){
            return 0;
        }

        return Math.max(getTreeDepth(root.left),getTreeDepth(root.right))+1;
    }
}

Golang代码实现

func isBalanced(root *TreeNode) bool {
    if root == nil{
        return true
    }

    leftDepth := getTreeDepth(root.Left)
    rightDepth := getTreeDepth(root.Right)

    if math.Abs(float64(leftDepth - rightDepth))>1{
        return false
    }

    return isBalanced(root.Left) && isBalanced(root.Right)

}

func getTreeDepth(root *TreeNode) int {
    if root == nil{
        return 0
    }

    leftDepth := getTreeDepth(root.Left)
    rightDepth := getTreeDepth(root.Right)

    if leftDepth < rightDepth{
        return rightDepth+1
    }else{
        return leftDepth+1
    }
}