Greatest difference Left and Right subtree count Node
Find the node with the max difference in the total number o0f descendents in its left subtree and right subtree.
Solution: sinking check, backtracking against global var
Base Case: if node == null: return 0;
Recursive rule:
From Children: receive number of nodes below
For current node: Check current left right diff against global max. If greater, update global max, add self to solution node
To parents: pass left count + right count + 1
public TreeNode solve(TreeNode root){
TreeNode[] solution = TreeNode[1]; //avoid pass by ref
int[] globalDiff = {Integer.MIN_VALUE};
maxlrdiffNode(root, globalDiff, solution);
return solution[0];
}
public int maxlrdiffNode(TreeNode root, int[] globalDiff, TreeNode[] sol){
if (root == null) return 0;
int leftCount = maxlrdiffNode(root.left);
int rightCount = maxlrdiffNode(root.right);
//check against global max
int curDiff = Math.abs(leftCount - rightCount);
if (curDiff > globalDiff[0]){
globalDiff[0] = curDiff;
sol[0] = root;
}
return leftCount + rightCount + 1;
}
Time Complexity: O(2^N) 2 recursive calls per node
Space Complexity: O(Height) recursive call stack
Last updated
Was this helpful?