本文共 1409 字,大约阅读时间需要 4 分钟。
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.
解题思路:
求左子树与右子树的深度之差,如果满足,分别递归左子树和右子树。但是这样有大量的重复计算,所以参考网上的一种做法,利用val来存深度,下面附上两次的代码。
public class Solution { public boolean isBalanced(TreeNode root) { if(root == null) return true; if(Math.abs(Depth(root.left)-Depth(root.right)) > 1) return false; return isBalanced(root.left) && isBalanced(root.right); } public int Depth(TreeNode root){ if(root == null) return 0; return Math.max(Depth(root.left)+1,Depth(root.right)+1); }}
改进解法:
public class Solution { public boolean isBalanced(TreeNode root) { if(root == null) return true; Depth(root); return balanced(root); } public boolean balanced(TreeNode root){ int l=0,r=0; if(root == null) return true; if(root.left != null) l = root.left.val; if(root.right != null) r = root.right.val; if(Math.abs(l-r) > 1) return false; return balanced(root.left) && balanced(root.right); } public int Depth(TreeNode root){ if(root == null) return 0; root.val = Math.max(Depth(root.left)+1,Depth(root.right)+1); return root.val; }
转载地址:http://rtivi.baihongyu.com/