- public class Solution {
- public boolean isBalanced(TreeNode root) {
- if (root == null) {
- return true;
- }
- boolean left = isBalanced(root.left);
- boolean right = isBalanced(root.right);
- int l = depth(root.left);
- int r = depth(root.right);
- return Math.abs(l - r) <= 1 && left && right;
- }
- public int depth(TreeNode root) {
- if (root == null) {
- return 0;
- }
- int left = depth(root.left);
- int right = depth(root.right);
- return Math.max(left, right) + 1;
- }
- }
这样的话,每个节点都要求一次 depth,depth 的时间复杂度是 O(n),所以总共的时间复杂度是 O(n^2)。
可以采取自下而上(bottom up)的方法。这样的话,时间复杂度是 O(n)。需要注意的是,只要左右有一个是 - 1,可以直接返回 - 1。不然的话可能出现两个子树的深度相同,但他们并不是平衡的。
- public class Solution {
- public boolean isBalanced(TreeNode root) {
- return depthDif(root) != -1;
- }
- public int depthDif(TreeNode root) {
- if (root == null) {
- return 0;
- }
- int left = depthDif(root.left);
- if (left == -1) {
- return -1;
- }
- int right = depthDif(root.right);
- if (right == -1) {
- return -1;
- }
- return Math.abs(left - right) <= 1 ? Math.max(left, right) + 1 : -1;
- }
- }
来源: http://www.bubuko.com/infodetail-2115528.html