JAVA O(n) solution based on Maximum Depth of Binary Tree


  • 14
    T
    public class Solution {
    private boolean result = true;
    
    public boolean isBalanced(TreeNode root) {
        maxDepth(root);
        return result;
    }
    
    public int maxDepth(TreeNode root) {
        if (root == null)
            return 0;
        int l = maxDepth(root.left);
        int r = maxDepth(root.right);
        if (Math.abs(l - r) > 1)
            result = false;
        return 1 + Math.max(l, r);
    }
    }

  • 0
    A

    It would be better if you call that height instead of maxDepth.


  • 4
    A

    A revision without using global value is following, but your solution is definitely better performed when running:

        public class Solution {
        public boolean isBalanced(TreeNode root) {
            if (root == null)
                return true;
            if (Math.abs(height(root.left)-height(root.right)) <= 1)
                return (isBalanced(root.left) && isBalanced(root.right));
            return false;
        }
        public int height(TreeNode root) {
            if (root == null)
                return 0;
            int left = height(root.left);
            int right= height(root.right);
            return (Math.max(left,right)+1);
            
        }
    }

  • 0
    D

    your solution will do lots of useless searching.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.