110. 平衡二叉树

题意：

解题思路：

思路：每个节点仅被遍历一次，且判断的复杂度是 O(1),所以总时间复杂度是 O(n)。
1. 对于根节点，分别求出左子树和右子树的深度，判断左右子树的高度差是否 <=1
2. 再对当前节点的左节点和右节点做同样操作。

PHP代码实现：

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {
    /**
     * @param TreeNode $root
     * @return Boolean
     */
    function isBalanced($root) {
       // $this->depthDiff($root);
        //return $this->diff < 2;
        if ($root == null) return true;
        return abs($this->getHeight($root->left) - $this->getHeight($root->right)) <= 1 &&
            $this->isBalanced($root->left) && $this->isBalanced($root->right);
    }
    function getHeight($root) {
        if ($root == null) return 0;
        $left = $this->getHeight($root->left);
        $right = $this->getHeight($root->right);
        return max($left, $right) + 1;
    }
    function depthDiff($root) {
        if ($root == null) return 0;
        $leftDepth = $this->depthDiff($root->left);
        $rightDepth = $this->depthDiff($root->right);
        $this->diff = max($this->diff, abs($leftDepth - $rightDepth));
        return max($leftDepth, $rightDepth) + 1;
    }
}

GO代码实现：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isBalanced(node *TreeNode) bool {
    return node == nil || math.Abs(height(node.Left)-height(node.Right)) < 2 && isBalanced(node.Left) && isBalanced(node.Right)
}
func height(node *TreeNode) float64 {
    if node == nil { return 0 }
    return math.Max(height(node.Left), height(node.Right)) + 1
}