Diameter of Binary Tree


  • 0

    Click here to see the full article post


  • 0
    W

    Is space complexity always expected to describe the worst case by default in the solution page?


  • 0

    @woofyzhao Generally yes, as usually Big O is most often discussed (compared to omega and theta)


  • 0
    J

    I think the space complexity is O(H), H is the height of the binary tree


  • 0

    @jocelynayoga Both examples are technically correct, your O(H) one is more precise though.


  • 0
    This post is deleted!

  • 0

    @Mr.Bin We calculated the number of nodes in the path, but the length is 1 minus this number. For example A--B--C there are 3 nodes but it is length 2.


  • 1
    A

    Why the solution with global variable is welcome on leetcode?
    Everyone know, it's a bad practice. And at the real interview, is better to think about code design and good practices as well, besides time and space complexity.
    Here is the solution without recursion and global variable:

    class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
    if (root == null) {
    return 0;
    }

        Stack<TreeNode> stack = new Stack<>();
        Map<TreeNode, Integer> maxLengthMap = new HashMap<>();
        stack.push(root);
        int maxDiameter = 0;
        boolean explored = false;
        while (stack.size() != 0) {
            TreeNode node = stack.peek();
            explored = (node.left != null && maxLengthMap.containsKey(node.left)) || node.left == null;
            if (!explored && node.left != null) {
                stack.push(node.left);
            }
            explored &= (node.right != null && maxLengthMap.containsKey(node.right)) || node.right == null;
            if (!explored && node.right != null) {
                stack.push(node.right);
            }
            //System.out.println("explored - " + explored + ", node val - " + node.val);
            if (explored) {
                int leftLength = maxLengthMap.getOrDefault(node.left, 0);
                if (node.left != null) {
                    leftLength += 1;
                }
                int rightLength = maxLengthMap.getOrDefault(node.right, 0);
                if (node.right != null) {
                    rightLength += 1;
                }
                
                //System.out.println("-- leftLength - " + leftLength + ", rightLength - " + rightLength);
                maxLengthMap.put(node, Math.max(leftLength, rightLength));
                int diameter = leftLength + rightLength;
                if (maxDiameter < diameter) {
                    maxDiameter = diameter;
                }
                stack.pop();
            }
        }
        return maxDiameter;
    }
    

    }


  • 0
    A

  • 0
    M

    My solution without using a global variable.

    class Solution {
        private class Int {
            int val;
            Int(int val) {
                this.val = val;
            }
        }
        public int diameterOfBinaryTree(TreeNode root) {
            if (root == null) return 0;
            Int ans = new Int(0);
            depthOfTree(root, ans);
            return ans.val;
        }
        
        public int depthOfTree(TreeNode root, Int ans) {
            if (root == null) return 0;
            int l = depthOfTree(root.left, ans);
            int r = depthOfTree(root.right, ans);
            ans.val = Math.max(ans.val, l + r);
            return 1 + Math.max(l, r);
        }
    }
    

  • 0
    L
    This post is deleted!

  • 0

    @lhx1031 Yes - both are technically correct.


  • 0
    G

    So time complexity N = number of node; while space complexity N = height of tree? Correct? I guess you could avoid use letter "N" for both, which is very misleading...


  • 0

    Instead of global variable ans, one can pass the as additional parameter

    int ans[] = new int[]{Integer.MIN_VALUE};
    

Log in to reply
 

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