平衡二叉树

1. 题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

2. 思路

获取树的高度二叉树的深度.md+左右子树高度差<=1

3. 实现

• java

public class 平衡二叉树
{
    public boolean IsBalanced_Solution(TreeNode root)
    {
        //检查参数
        if (root == null)
        {
            return true;
        }
        //获取左子树高度，右子树高度，差值小于1
        return Math.abs(this.getTreeDepth(root.right) - this.getTreeDepth(root.left)) <= 1 &&
            //并且 左子树同样的逻辑
            this.IsBalanced_Solution(root.left) &&
            //并且 右子树同样的逻辑
            this.IsBalanced_Solution(root.right);
    }

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

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

• go

/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 *
 * @param pRoot TreeNode类
 * @return bool布尔型
 */
//时间复杂度：O(N²)
//空间复杂度：O(N)
func IsBalanced_Solution(pRoot *TreeNode) bool {
	if pRoot == nil {
		return true
	}

	return abs(getHeight(pRoot.Left)-getHeight(pRoot.Right)) < 2 && IsBalanced_Solution(pRoot.Left) && IsBalanced_Solution(pRoot.Right)
}

func getHeight(node *TreeNode) int {
	if node == nil {
		return 0
	}
	return 1 + max(getHeight(node.Left), getHeight(node.Right))
}

func abs(v int) int {
	if v < 0 {
		return -v
	}
	return v
}


func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

4. 参考

• 平衡二叉树_牛客网
• 110. 平衡二叉树 - 力扣（LeetCode）