Traverse with memory, 17 ms.


  • 0

    Well, in terms of complexity, this method should be O(N), but the performance based on OJ test case is not as expected.

    public boolean isBalanced1(TreeNode root) {
            if (root == null) return true;
            HashMap<TreeNode, Integer> mem = new HashMap<>();
            return Math.abs( depthMem(root.left, mem) - depthMem(root.right, mem) ) <= 1
                    && isBalanced1(root.left) && isBalanced1(root.right);
        }
    
        // return the depth of the tree
        private int depth(TreeNode root) {
            if (root == null) return 0;
            return Math.max(depth(root.left), depth(root.right)) + 1;
        }
    
        private int depthMem(TreeNode root, HashMap<TreeNode, Integer> mem) {
            if (root == null) return 0;
    
            int left, right;
            if (mem.containsKey(root.left))
                left = mem.get(root.left);
            else
                left = depthMem(root.left, mem);
    
            if (mem.containsKey(root.right))
                right = mem.get(root.right);
            else
                right = depthMem(root.right, mem);
    
            int tmp = Math.max(left, right) + 1;
            mem.put(root, tmp);
    
            return tmp;
        }
    
    

Log in to reply
 

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