@fahsrouq Space complexicity is logN, so I guess here, it's actually the "height" of the tree?
gerrybio
@gerrybio
Posts made by gerrybio

RE: My recursive solution(Java)

RE: My recursive solution(Java)
Personally I think this is the best solution, but is recursion using constant extra space?
What's the time complexicity here? 
Simple JAVA DFS method.
Very simple question, if you think correctly.
 Calculate the sum of all node values.
 Write dfs method to calculate the sum of particular root's subtree. As long as there's ONE root's subtree sum equals to sum/2; we'll return true.
class Solution { public boolean checkEqualTree(TreeNode root) { if (root.left == null && root.right == null) return false; List<Integer> list = new ArrayList<>(); int sum = treeSum(root, list); if (sum % 2 != 0) return false; // sum has to be even to return true; //Also pay attention, sum could be negative, 1 % 2 = 1; so your if condition should be "!= 0" sum /= 2; for (int x : list) { if (x == sum) return true; } return false; } // This method has two functions: 1. return total sum; 2. Keep track of the sum of subtree of each node. private int treeSum(TreeNode root, List<Integer> list) { if (root == null) return 0; int sum = root.val + treeSum(root.left, list) + treeSum(root.right, list); list.add(sum); return sum; } }

BFS by using two lists to keep level node index
 Basic idea is to keep track of "width" by maintaining two lists, which represents node index of previous and current levels.
 Example:
Tree Index 1 0 / \ / \ 3 2 0 1 / \ / \ /\ /\ 5 X X 9 0 1 2 3 ##pre level index : i ##cur level index : 2i and 2i + 1
class Solution { public int widthOfBinaryTree(TreeNode root) { if (root == null) return 0; // If root is not null, we could do the following. Queue<TreeNode> q = new LinkedList<>(); List<Integer> pre = new ArrayList<>(); // Apply two lists(pre and cur) to keep track of nodes index of each level. q.offer(root); pre.add(0); int maxWidth = 1; while(!q.isEmpty()) { List<Integer> cur = new ArrayList<>(); // Apply two lists(pre and cur) to keep track of nodes index of each level. int size = q.size(); for (int i = 0; i < size; i++) { // Traverse each node of the previous level. TreeNode tmp = q.poll(); if (tmp.left != null) { q.offer(tmp.left); // If not null, add node; cur.add(2 * pre.get(i)); // Calculate current level node index according to previous level index record. } if (tmp.right != null) { q.offer(tmp.right); cur.add(2 * pre.get(i) + 1); } } int n = cur.size(), width = 0; if (n != 0) { width = cur.get(n  1)  cur.get(0) + 1; // Largest nonnull node index  smallest nonnull node index; maxWidth = Math.max(maxWidth, width); } else break; pre = cur; // current level node index becomes previous record for the next loop. } return maxWidth; } }

RE: What is the difference between (low + high) / 2 and low + (high  low) / 2?
l + (h  l) / 2 could help you avoid overflow of 32big integer.

RE: A java solution based on Priority Queue
when people talking about time complexity; say, O(nlogk)
Can we first clarify what is "n" please?
If n is total number of numbers of all lists, then it's nlogk;
if n is average length of each list, then it's nklogk;
Without clarification it'll cause lots of confusion. 
RE: Accepted short solution in Java
public int maxPathSum(TreeNode root) { int res = Integer.MIN_VALUE; maxBranch(root, res); return res; } private int maxBranch(TreeNode root, int res) { if (root == null) return 0; int left = Math.max(0, maxBranch(root.left, res)); int right = Math.max(0, maxBranch(root.right, res)); res = Math.max(res, left + right + root.val); return Math.max(left, right) + root.val; }
Here's my code. One dump dump question is:
Why can't we pass in directly "int res" to "maxBranch" to update max? I tried that yes it's not working. We'll have to replace "int res" with "int[0] res" ? 
RE: Java Concise Postorder Traversal Solution
@sailorconangmail.com
I have the same question. If you tried "left + val + right"
You'll get error for the test case:
[0,0,0,0,null,null,0,null,null,null,0]In this case, left most subtree is:
0 / \ 0 # / \ # #
So inorder traversal will be : [#0#0#]
While right most subtree is:
0 / \ # 0 / \ # #
inorder traversal will also be : [#0#0#]
But obviously these two subtrees are different; but will be considered as the same given the same string by inorder traversal.
This is caused by symmetric structures of this special case.
And if you use either postorder or preorder, you could distinguish the two.

RE: Java DP Solution
@ho_chung
Thanks a lot! Makes a lot of sense. dp[i] is actually sum of all prime factors! And for prime factors, dp[i] = i !