LeetCode -- Balanced Binary Tree
题目描述:
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
就是判断一棵树,是否为平衡树。
平衡树的定义就是,左右子树的高度差不能超过1。
思路:
判断每个节点是否平衡
对于任何一个节点,判断左右是否平衡。仅当左右子树都平衡时,当前树才算平衡。
分别求出左右子树的高度,返回Math.Max(左子树高度,右子树高度)+1
实现代码:
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
就是判断一棵树,是否为平衡树。
平衡树的定义就是,左右子树的高度差不能超过1。
思路:
判断每个节点是否平衡
对于任何一个节点,判断左右是否平衡。仅当左右子树都平衡时,当前树才算平衡。
分别求出左右子树的高度,返回Math.Max(左子树高度,右子树高度)+1
实现代码:
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public bool IsBalanced(TreeNode root)
{
if(root == null || root.left == null && root.right == null){
return true;
}
var l = Depth(root.left);
var r = Depth(root.right);
if(Math.Abs(l-r) > 1){
return false;
}
var bLeft = IsBalanced(root.left);
var bRight = IsBalanced(root.right);
return bLeft && bRight;
}
public int Depth(TreeNode node)
{
if(node == null){
return 0;
}
var l = Depth(node.left);
var r = Depth(node.right);
var len = Math.Max(l,r);
return len + 1;
}
}