Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:
The root is the maximum number in the array.
The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.
Divide and Conquer, use getTree construct tree and findMax find max index.
Average time O(nlogn), worst case O(n^2)
public TreeNode constructMaximumBinaryTree(int[] nums) {
return getTree(nums, 0, nums.length);
}
private TreeNode getTree(int[] nums, int start, int end){
if(start == end) return null;
int max_idx = findMax(nums, start, end);
TreeNode node = new TreeNode(nums[max_idx]);
node.left = getTree(nums, start, max_idx);
node.right = getTree(nums, max_idx+1, end);
return node;
}
private int findMax(int[] nums, int start, int end){
int max = nums[start];
int index = start;
for(int i= start+1; i<end; i++){
if(nums[i] > max){
max = nums[i];
index = i;
}
}
return index;
}
222 Count Complete TreeNode
Given a complete binary tree, count the number of nodes.
Time O(n)
public int countNodes(TreeNode root) {
if(root == null) return 0;
return 1 + countNodes(root.left) + countNodes(root.right);
}
每一層leftNode or rightNode有一個是complete tree, 總共logn層
Time O(logn)
public int countNodes(TreeNode root) {
int left = leftHeight(root);
int right = rightHeight(root);
if(left == right) return (1 << left) -1;
return 1 + countNodes(root.left) + countNodes(root.right);
}
private int leftHeight(TreeNode node){
int height = 0;
while(node != null){
height++;
node = node.left;
}
return height;
}
private int rightHeight(TreeNode node){
int height = 0;
while(node != null){
height++;
node = node.right;
}
return height;
}
863. All Nodes Distance K in Binary Tree
Return a list of the values of all nodes that have a distance K from the target node.
"""
分target以上level跟以下level討論
1. 以下level找到distance為k的node
2. 往上recursive找到距離為k的upper level node, 繼續往上，網left and right node找
"""
class Solution:
def distanceK(self, root: TreeNode, target: TreeNode, K: int) -> List[int]:
self.ans = []
self. dfs(root, target, K)
return self.ans
# return the distance to node target
def dfs(self, node, target, K):
if not node:
return -1
elif node == target:
self.addNodes(node, K)
return 1
else:
L, R = self.dfs(node.left, target, K), self.dfs(node.right, target, K)
if L != -1 and L <= K:
if L == K:
self.ans.append(node.val)
# target 在left child, 往 right child 移動
self.addNodes(node.right, K-L-1)
return L+1
elif R != -1 and R<=K:
if R == K:
self.ans.append(node.val)
self.addNodes(node.left, K-R-1)
return R+1
else:
return -1
def addNodes(self, node, K):
if not node:
return
if K==0:
self.ans.append(node.val)
self.addNodes(node.left, K-1)
self.addNodes(node.right, K-1)
1145. Binary Tree Coloring Game
Two players play a turn based game on a binary tree. We are given the root of this binary tree, and the number of nodes n in the tree. n is odd, and each node has a distinct value from 1 to n.
The first player colors the node with value x red, and the second player colors the node with value y blue.
return if second player can win the game
The best chance to win is choosing node next to x, the players 1 can't cross this node, players can take the child nodes all.
3 possibilities: left child, right child, and parent node
Return if candidate subtree is greater than total number of nodes
def btreeGameWinningMove(self, root: TreeNode, n: int, x: int) -> bool:
l, r = 0, 0
def count(node):
nonlocal l, r
if not node: return 0
left = count(node.left)
right = count(node.right)
# meet x node, update the left child and right child candidate
if node.val == x:
l, r = left, right
return 1 + left + right
total = count(root)
return max(max(l, r), n - l - r - 1) > total // 2
