93.Balanced Binary Tree-平衡二叉树（容易题）

本文主要是介绍93.Balanced Binary Tree-平衡二叉树（容易题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

平衡二叉树

1. 题目

   给定一个二叉树,确定它是高度平衡的。对于这个问题,一棵高度平衡的二叉树的定义是：一棵二叉树中每个节点的两个子树的深度相差不会超过1。

2. 样例

   给出二叉树 A={3,9,20,#,#,15,7}, B={3,#,20,15,7}
   
   二叉树A是高度平衡的二叉树，但是B不是

3. 题解

递归计算任意节点左右子树的高度值进行比较。

/*** Definition of TreeNode:* public class TreeNode {*     public int val;*     public TreeNode left, right;*     public TreeNode(int val) {*         this.val = val;*         this.left = this.right = null;*     }* }*/
public class Solution {/*** @param root: The root of binary tree.* @return: True if this Binary tree is Balanced, or false.*/public boolean isBalanced(TreeNode root) {if (root == null){return true;}int left = getDepth(root.left);int right = getDepth(root.right);if (Math.abs(left - right) <= 1){return isBalanced(root.left) && isBalanced(root.right);}return false;}private int getDepth(TreeNode root){if(root ==null){return 0;}int left = getDepth(root.left);int right = getDepth(root.right);return Math.max(left,right)  + 1;}
}

Last Update 2016.9.2

这篇关于93.Balanced Binary Tree-平衡二叉树（容易题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---