Balanced Binary Tree
给一个二叉树, 看看是不是平衡的bst. 平衡的bst的定义是两侧的高度差不超过1. 所以就每个子树看一下呗
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public boolean isBalanced(TreeNode root) { if(root == null) return true; int l = height(root.left); int r = height(root.right); if(Math.abs(l-r) > 1) return false; return isBalanced(root.left) && isBalanced(root.right); } public int height(TreeNode root){ if(root == null) return 0; return Math.max(height(root.left),height(root.right))+1; } } |