LeetCode：平衡二叉树【110】

题目描述

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

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

3   / \  9  20    /  \   15   7

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

1      / \     2   2    / \   3   3  / \ 4   4

返回 false 。

题目分析

　　解法的整体过程为二叉树的后序遍历，对任何一个节点node来说，先遍历node的左子树，遍历过程中收集两个信息，node的左子树是否为平衡二叉树，node的左子树最深处level。如果发现左子树不是平衡二叉树，无需进行任何后续过程，此时返回什么已经不重要，因为已经发现整棵树不是平衡二叉树，退出遍历过程。

　　如果node的右子树也是平衡二叉树，此时就看左右子树的level差的绝对值是否大于1，大于1说明不是平衡二叉树，如果不大于1，则返回较大的一个。

Java题解

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public boolean isBalanced(TreeNode root) {        boolean[] res = new boolean[1];        res[0] = true;        getHeight(root,1,res);        return res[0];    }        public int getHeight(TreeNode head,int level,boolean[] res)    {        if(head==null)            return level;        int lh = getHeight(head.left,level+1,res);        if(!res[0])            return level;        int rh = getHeight(head.right,level+1,res);        if(!res[0])            return level;        if(Math.abs(lh-rh)>1)            res[0]=false;        return Math.max(lh,rh);    }}