Tree
Binary Tree Traversal
# ITERATION
def preorderTraversal(self, root: TreeNode) -> List[int]:
stack = []
res = []
if not root:
return res
stack.append(root)
while stack:
curt = stack.pop()
res.append(curt.val)
if curt.right:
stack.append(curt.right)
if curt.left:
stack.append(curt.left)
return res
# RECURSION
def preorderTraversal(self, root: TreeNode) -> List[int]:
res = []
self.helper(root, res)
return res
def helper(self, root, res):
if root == None:
return
res.append(root.val)
self.helper(root.left, res)
self.helper(root.right, res)
# ITERATION
def inorderTraversal(self, root: TreeNode) -> List[int]:
stack = []
res = []
if not root:
return res
self.addLeft(root, stack)
while stack:
curt = stack.pop()
res.append(curt.val)
self.addLeft(curt.right, stack)
return res
def addLeft(self, curt, stack):
while curt:
stack.append(curt)
curt = curt.left
# RECURSION
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
self.helper(root, res)
return res
def helper(self, root, res) -> None:
if root == None:
return
self.helper(root.left, res)
res.append(root.val)
self.helper(root.right, res)
# ITERATION
def postorderTraversal(self, root: TreeNode) -> List[int]:
stack = []
res = []
if not root:
return res
stack.append(root)
while stack:
curt = stack.pop()
res.append(curt.val)
if curt.left:
stack.append(curt.left)
if curt.right:
stack.append(curt.right)
res.reverse()
return res
# RECURSION
def postorderTraversal(self, root: TreeNode) -> List[int]:
res = []
self.helper(root, res)
return res
def helper(self, root, res):
if root == None:
return
self.helper(root.left, res)
self.helper(root.right, res)
res.append(root.val)
Swap left node with right node.
def invertTree(self, root: TreeNode) -> TreeNode:
self.helper(root)
return root
def helper(self, root) :
if not root:
return
temp = root.right
root.right = root.left
root.left = temp
self.helper(root.left)
self.helper(root.right)
Top - down
res = 0
def maxDepth(self, root: TreeNode) -> int:
self.helper(root, 1)
return self.res
def helper(self, curt, depth):
if not curt:
return
self.res = max(self.res, depth)
self.helper(curt.left, depth + 1)
self.helper(curt.right, depth + 1)
Bottom - up
def maxDepth(self, root: TreeNode) -> int:
return self.helper(root, 1)
def helper(self, curt, depth):
if not curt:
return 0
L = self.helper(curt.left, depth + 1)
R = self.helper(curt.right, depth + 1)
return max(max(L, R), depth)
public int maxDepth(Node root) {
return helper(root);
}
private int helper(Node curt) {
if (curt == null) return 0;
int max = 0;
for (Node child : curt.children) {
max = Math.max(max, helper(child));
}
return max + 1;
}
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
if (root == null) return res;
dfs(root, new StringBuilder(), res);
return res;
}
private void dfs(TreeNode root, StringBuilder sb, List<String> res) {
if (root == null) return;
if (root.left == null && root.right == null) {
sb.append(root.val);
res.add(sb.toString());
return;
}
sb.append(root.val).append("->");
int len = sb.length();
dfs(root.left, sb, res);
sb.setLength(len);
dfs(root.right, sb, res);
}
public boolean isSubtree(TreeNode s, TreeNode t) {
if (s == null) return false;
return isSame(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
}
private boolean isSame(TreeNode s, TreeNode t) {
if (s == null && t == null) return true;
if (s == null || t == null) return false;
return s.val == t.val && isSame(s.left, t.left) && isSame(s.right, t.right);
}
把左边和右边的结果放到一个variable存一下,看看是不是哪边=-1或者两边的差大约1
res = True
def isBalanced(self, root: TreeNode) -> bool:
if not root:
return True
self.helper(root)
return self.res
def helper(self, curr):
if not curr:
return 0
L = self.helper(curr.left)
R = self.helper(curr.right)
self.res = (abs(L - R) <= 1) and self.res
return max(L, R) + 1
Bottom-up and detect the node is on both L and R or just one side?
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) return root;
TreeNode L = lowestCommonAncestor(root.left, p, q);
TreeNode R = lowestCommonAncestor(root.right, p, q);
if (L != null && R != null) {
return root;
} else if (L == null && R != null) {
return R;
} else if (L != null && R == null) {
return L;
}
return null;
}
Traverse to see if a leaf node value equals sum, deduct current node val on each node.
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) return false;
if (root.left == null && root.right == null) return root.val == sum;
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
Traverse down the tree, add new node value to the list. Deep copy current list on each level.
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> result = new ArrayList<>();
helper(root, sum, new ArrayList<>(), result);
return result;
}
private void helper(TreeNode root,
int sum,
List<Integer> curtList,
List<List<Integer>> res) {
if (root == null) return;
curtList.add(root.val);
if (root.left == null && root.right == null) {
if (sum == root.val) {
res.add(new ArrayList<>(curtList));
}
return;
}
helper(root.left, sum - root.val, new ArrayList<>(curtList), res);
helper(root.right, sum - root.val, new ArrayList<>(curtList), res);
}
This version of backtracking. No need to make a deep-copy of the current list.
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
helper(root, sum, new ArrayList<>(), result);
return result;
}
private void helper(TreeNode root,
int sum,
List<Integer> curtList,
List<List<Integer>> res) {
if (root.left == null && root.right == null) {
if (sum == root.val) {
curtList.add(root.val);
res.add(new ArrayList<>(curtList));
curtList.remove(curtList.size() - 1);
}
return;
}
curtList.add(root.val);
if (root.left != null) helper(root.left, sum - root.val, curtList, res);
if (root.right != null) helper(root.right, sum - root.val, curtList, res);
curtList.remove(curtList.size() - 1);
}
This question asks all Path Sum starting any node to any node, but only go downwards. It can be easily achieved by using the previous method + start fresh traversal at each node.
T: O(n^2)
public int pathSum(TreeNode root, int sum) {
if (root == null) return 0;
return helper(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
}
private int helper(TreeNode root, int sum) {
if (root == null) return 0;
int count = 0;
if (sum == root.val) count += 1;
count += helper(root.left, sum - root.val);
count += helper(root.right, sum - root.val);
return count;
}
This can also achieved by using PrefixSum. Maintain a current sum and count of the prefix sum numbers in a HashMap ( key : the prefix sum, value : how many ways get to this prefix sum). Add the node value to the prefix sum. curtSum - target
indicates that theres is a range sum in the path equals to target. Put curtSum in the map. When backtracking, reduce a count by 1 as it shouldn't count the current node anymore.
This method is very similar with LC560.
public int pathSum(TreeNode root, int sum) {
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
return helper(root, sum, 0, map);
}
private int helper(TreeNode root,
int target,
int curtSum,
Map<Integer, Integer> map) {
if (root == null) return 0;
curtSum += root.val;
int count = map.getOrDefault(curtSum - target, 0);
map.put(curtSum, map.getOrDefault(curtSum, 0) + 1);
count += helper(root.left, target, curtSum, map) + helper(root.right, target, curtSum, map);
map.put(curtSum, map.get(curtSum) - 1);
return count;
}
int max = Integer.MIN_VALUE;
public int longestConsecutive(TreeNode root) {
if (root == null) return 0;
helper(root, 0 , root.val);
return max;
}
private void helper(TreeNode root, int curtLength, int target) {
if (root == null) return;
curtLength = (root.val == target) ? curtLength + 1 : 1;
max = Math.max(max, curtLength);
helper(root.left, curtLength, root.val + 1);
helper(root.right, curtLength, root.val + 1);
}
public int longestConsecutive(TreeNode root) {
if (root == null) {
return 0;
}
return helper(root).max;
}
private Result helper(TreeNode root) {
if (root == null) {
return new Result(0, 0, 0, null);
}
Result L = helper(root.left);
Result R = helper(root.right);
int Linc = 1, Ldec = 1, Rinc = 1, Rdec = 1;
if (L.node != null) {
if (L.node.val == root.val + 1) {
Ldec = L.dec + 1;
} else if (L.node.val == root.val - 1) {
Linc = L.inc + 1;
}
}
if (R.node != null) {
if (R.node.val == root.val + 1) {
Rdec = R.dec + 1;
} else if (R.node.val == root.val - 1) {
Rinc = R.inc + 1;
}
}
int max = 1;
int maxInc = Math.max(Linc, Rinc), maxDec = Math.max(Ldec, Rdec);
max = Math.max(Math.max(maxInc, maxDec), max);
max = Math.max(Math.max(Linc + Rdec - 1, Rinc + Ldec - 1), max);
max = Math.max(Math.max(L.max, R.max), max);
return new Result(maxInc, maxDec, max, root);
}
class Result {
int inc, dec;
int max;
TreeNode node;
Result(int inc, int dec, int max, TreeNode node) {
this.inc = inc;
this.dec = dec;
this.max = max;
this.node = node;
}
}
int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
helper(root);
return max;
}
private int helper(TreeNode root) {
if (root == null) return 0;
int left = Math.max(helper(root.left), 0);
int right = Math.max(helper(root.right), 0);
max = Math.max(max, left + right + root.val);
return Math.max(left, right) + root.val;
}
Bottom-up and return the longest path from bottom, which is Math.max(L, R) + 1
. In addition, each node can be a potential root of the best result, therefore update the global max at each node by max = Math.max(L + R, max)
T: O(n) S: O(n)
Top - down
int max = 0;
Map<TreeNode, Integer> map;
public int diameterOfBinaryTree(TreeNode root) {
if (root == null) return 0;
map = new HashMap<>();
helper(root);
return max;
}
private void helper(TreeNode root) {
if (root == null) return;
max = Math.max(max, maxPath(root.left) + maxPath(root.right));
helper(root.left);
helper(root.right);
}
private int maxPath(TreeNode root) {
if (root == null) return 0;
if (map.containsKey(root)) return map.get(root);
int res = Math.max(maxPath(root.left), maxPath(root.right)) + 1;
map.put(root, res);
return res;
}
Bottom - up
int max = 0;
public int diameterOfBinaryTree(TreeNode root) {
helper(root);
return max;
}
private int helper(TreeNode root) {
if (root == null) return 0;
int L = helper(root.left);
int R = helper(root.right);
max = Math.max(L + R, max);
return Math.max(L, R) + 1;
}
117. Populating Next Right Pointers in Each Node II
Level order traversal and connect next nodes
T: O(n) S: O(n)
public Node connect(Node root) {
if (root == null) return null;
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
Node prev = queue.poll();
if (prev.left != null) queue.offer(prev.left);
if (prev.right != null) queue.offer(prev.right);
for (int i = 1; i < size; i++) {
Node curt = queue.poll();
if (curt.left != null) queue.offer(curt.left);
if (curt.right != null) queue.offer(curt.right);
prev.next = curt;
prev = curt;
}
}
return root;
}
Iterative connection:
head
to represent the first node of the next levelprev
to represent the previous node (similar as linkedlist)curt
to represent the current node (similar as linkedlist)
Use curt to traverse in each level, and connect the children. If the left/right child exist, and prev is not null, then use prev to connect. Otherwise if prev is null, it means that node is head.
T: O(n) S: O(1)
public Node connect(Node root) {
if (root == null) return null;
Node head = root;
Node prev = null;
Node curt = null;
while (head != null) {
curt = head;
prev = null;
head = null;
while (curt != null) {
if (curt.left != null) {
if (prev != null) {
prev.next = curt.left;
} else {
head = curt.left;
}
prev = curt.left;
}
if (curt.right != null) {
if (prev != null) {
prev.next = curt.right;
} else {
head = curt.right;
}
prev = curt.right;
}
curt = curt.next;
}
}
return root;
}
Top-down traverse. Map the tree node position to an array, which means the left node is pos * 2
and right node pos is pos * 2 + 1
. In preorder traversal, you will encounter the left most node, hence record the pos
of the node in the Hashmap.
For the rest of nodes, the width will be right pos - left + 1
. Update the global max
on each node.
int max = 1;
public int widthOfBinaryTree(TreeNode root) {
if (root == null) return 0;
Map<Integer, Integer> map = new HashMap<>();
helper(root, map, 0, 0);
return max;
}
private void helper(TreeNode root,
Map<Integer, Integer> map,
int depth,
int pos) {
if (root == null) return;
map.putIfAbsent(depth, pos);
max = Math.max(max, pos - map.get(depth) + 1);
helper(root.left, map, depth + 1, pos * 2);
helper(root.right, map, depth + 1, pos * 2 + 1);
}
Traversal Time Complexity:
For a Graph, the complexity of a Depth First Traversal is O(n + m), where n is the number of nodes, and m is the number of edges.
Since a Binary Tree is also a Graph, the same applies here. The complexity of each of these Depth-first traversals is O(n+m).
Since the number of edges that can originate from a node is limited to 2 in the case of a Binary Tree, the maximum number of total edges in a Binary Tree is n-1, where n is the total number of nodes.
The complexity then becomes O(n + n-1), which is O(n).
Build coordinates of each node, sort by y and node val.
int minX = 0;
public List<List<Integer>> verticalTraversal(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
Map<Integer, List<Node>> map = new HashMap<>();
dfs(root, 0, 0, map);
for (int key : map.keySet()) {
Collections.sort(map.get(key), new Comparator<Node>(){
public int compare(Node a, Node b) {
if (a.y == b.y) return a.node.val - b.node.val;
return a.y - b.y;
}
});
int xIndex = map.get(key).get(0).x - minX;
while (res.size() <= xIndex) res.add(new ArrayList<>());
for (Node n : map.get(key)) {
res.get(xIndex).add(n.node.val);
}
}
return res;
}
private void dfs(TreeNode root, int x, int y, Map<Integer, List<Node>> map) {
if (root == null) return;
minX = Math.min(minX, x);
map.putIfAbsent(x, new ArrayList<>());
Node node = new Node(root, x, y);
map.get(x).add(node);
dfs(root.left, x - 1, y + 1, map);
dfs(root.right, x + 1, y + 1, map);
}
class Node {
int x, y;
TreeNode node;
Node(TreeNode n, int x, int y) {
this.node = n;
this.x = x;
this.y = y;
}
}
Delete a Node in Binary Tree
Starting at root, find the deepest and rightmost node in binary tree and node which we want to delete.
Replace the deepest rightmost node’s data with node to be deleted.
Then delete the deepest rightmost node.
Binary Search Tree
Four Key factors:
IS NOT IN A TREE: do nothing
IS A LEAF: just remove it
HAS ONLY ONE CHILD: Copy the child to the node and delete the child
HAS TWO CHILDREN: Find inorder successor of the node. Copy contents of the inorder successor to the node and delete the inorder successor. Note that inorder predecessor can also be used.
450. Delete Node in a BST
250. Count Univalue Subtrees
用Boolean来记录左边和右边的结果,看是不是univalue subtrees,如果左边右边都是的话,Count++,返回True。如果左边右边都是,但是两边有Null或者值不等于Root Value,返回False
if (node == null) return true;
boolean left = helper(node.left);
boolean right = helper(node.right);
if (left && right) {
if ((node.left != null && node.left.val != node.val) || (node.right != null && node.right.val != node.val)) {
return false;
}
count++;
return true;
}
return false;
366. Find Leaves of Binary Tree
用Level来记录从下往上的层数,最下面Null是-1,往上是0,这样的话可以用res.get(level).add(curt.val) 来往结果里加值。如果结果里Array数小于level + 1说明没有那个Array,要建个新的
if (curt == null) return -1;
int level = 1 + Math.max(helper(curt.left, res), helper(curt.right, res));
if (res.size() < level + 1) {
res.add(new ArrayList<>());
}
res.get(level).add(curt.val);
return level;
337. House Robber III
有很多重复运算,因为要先算所有include 自己的情况,然后exclude自己的情况,取Max。解
Improvement: 用Hashmap可以记录每个点的max
Improvement: 用Array
107. Binary Tree Level Order Traversal II
用Queue的话,和I不一样的地方就是这个在上面插入List。result.add(0,list);
用Recursion,
if(level >= list.size()) {
list.add(0, new LinkedList<Integer>());
}
levelMaker(list, root.left, level+1);
levelMaker(list, root.right, level+1);
list.get(list.size()-level-1).add(root.val);
199. Binary Tree Right Side View
Queue是用i == qSize - 1判断最右边
Recursion用currDepth == result.size()判断最右边,然后每下一层depth + 1
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
dfs(root, 0, res);
return res;
}
private void dfs(TreeNode root, int depth, List<Integer> res ) {
if (root == null) return;
if (depth == res.size()) {
res.add(root.val);
}
dfs(root.right, depth + 1, res);
dfs(root.left, depth + 1, res);
}
Bottom up to get the answer.
double res = Double.MIN_VALUE;
public double maximumAverageSubtree(TreeNode root) {
helper(root);
return res;
}
private int[] helper(TreeNode root) {
if (root == null) {
return new int[2];
}
int[] L = helper(root.left);
int[] R = helper(root.right);
int sum = L[0] + R[0] + root.val;
int count = L[1] + R[1] + 1;
res = Math.max(res, (double)sum / (double)count);
return new int[]{sum, count};
}
114.Flatten Binary Tree to Linked List
108.Convert Sorted Array to Binary Search Tree
Use left, right, mid
If left > right -> return null
If left == right -> return nums[left]
Return root = new TreeNode(nums[mid]);
Root.left = helper(nums, left, mid - 1);
Root.right = helper(nums, mid + 1, right);
pre-order → build tree
post-order array → build tree
109. Convert Sorted List to Binary Search Tree
Get size of the sorted list
In recursive function:
TreeNode left = helper(0 to mid - 1)
find mid, construct the node by using mid
Node.left = left;
Node right = helper(mid + 1, end);
297.Serialize and Deserialize Binary Tree
Construct a tree by using Root, left, right
If (root == null) return “null” + “,”
Str += String.valueOf(root.val) + “,”; Str = helper(root.left, str); str = helper(root.right, str);
When de-serialization, split str by “,” and convert to LinkedList;
Construct root from the first value, remove first value from List
Go left and right
173. Binary Search Tree Iterator
BST to Linkedlist by using Inorder traversal, create an iterator from the linkedlist
Stack
Morris traversal. Solution, Explanation
230. Kth Smallest Element in a BST
Stack
Morris
Iterative
270. Closest Binary Search Tree Value
272. Closest Binary Search Tree Value II
99. Recover Binary Search Tree
Morris Traversal
Traverse to left and your returned non-null node is your new root. Connect the right of the current node to the left of the left node, connect current to the right of the left node. Erase root's left and right to null. Return new root.
public TreeNode upsideDownBinaryTree(TreeNode root) {
if (root == null) return null;
if (root.left == null && root.right == null) {
return root;
}
TreeNode newRoot = upsideDownBinaryTree(root.left);
root.left.left = root.right;
root.left.right = root;
root.left = null;
root.right = null;
return newRoot;
}
114. Flatten Binary Tree to Linked List
255. Verify Preorder Sequence in Binary Search Tree
Top-down method may take more than O(n) time. Use Bottom-up, and store if the branch is a BST, size of the BST, the min and max node. Return to the previous level. At each node:
check if the left result and right result is a BST, if one of them is not, return the best count of left and right
check if the curt.val exceed the range of left and right, if yes, return the best count of left and right
return the result if current node is a root of a BST.
public int largestBSTSubtree(TreeNode root) {
return helper(root).count;
}
private Result helper(TreeNode curt) {
if (curt == null) return new Result(true, 0);
Result L = helper(curt.left);
Result R = helper(curt.right);
Result res = new Result(false, Math.max(L.count, R.count));
if (!L.isBST || !R.isBST) {
return res;
}
if ((L.max != null && L.max.val >= curt.val)
|| (R.min != null && R.min.val <= curt.val)) {
return res;
}
res.isBST = true;
res.count = L.count + R.count + 1;
res.max = R.max != null ? R.max : curt;
res.min = L.min != null ? L.min : curt;
return res;
}
class Result {
int count;
boolean isBST;
TreeNode max;
TreeNode min;
public Result(boolean isBST, int count) {
this.isBST = isBST;
this.count = count;
this.max = null;
this.min = null;
}
}
222. Count Complete Tree Nodes
105. Construct Binary Tree from Preorder and Inorder Traversal
106. Construct Binary Tree from Inorder and Postorder Traversal
116 .Populating Next Right Pointers in Each Node
Level order traversal, use a Prev == null before each level, if (prev != null) prev.next = curt, then curt = prev;
314. Binary Tree Vertical Order Traversal
Use Map<Integer, List<Integer>> to store col and related nodes;
Add two queues, one to store nodes, the other one to store col, poll from two nodes at the same time. Default col with 0;
Keep a min and max to store the min and max col number
Convert the map to List<List<Integer>>
95. Unique Binary Search Trees II
用从1到N的数Construct所有Unique的BST
If n == 0 return empty result
Use helper function to iterate i through from 1 to n. Use another two iterations from 1 to i - 1 to create lefts and and i + 1 to n to create rights. Create node by using i, then attach root.left as left, root.right as right.
331. Verify Preorder Serialization of a Binary Tree
Using stack
Bottom-up approach. If curt need to be deleted, add left and right to the list.
public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
Set<Integer> set = new HashSet<>();
for (int node : to_delete) {
set.add(node);
}
List<TreeNode> res = new ArrayList<>();
root = helper(root, set, res);
if (root != null) res.add(root);
return res;
}
private TreeNode helper(TreeNode curt,
Set<Integer> toDelete,
List<TreeNode> list) {
if (curt == null) return null;
TreeNode L = helper(curt.left, toDelete, list);
TreeNode R = helper(curt.right, toDelete, list);
if (toDelete.contains(curt.val)) {
if (L != null) list.add(L);
if (R != null) list.add(R);
return null;
}
curt.left = L;
curt.right = R;
return curt;
}
int total = 0;
public int distributeCoins(TreeNode root) {
helper(root);
return total;
}
public int helper(TreeNode root) {
if (root == null) {
return 0;
}
int L = helper(root.left);
int R = helper(root.right);
int res = L + R + root.val;
if (res == 1) {
return 0;
}
total += Math.abs(res - 1);
return res - 1;
}
Convert tree to graph and BFS level order traversal.
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
Map<TreeNode, Set<TreeNode>> map = new HashMap<>();
traverse(root, null, map);
Queue<TreeNode> q = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
List<Integer> res = new ArrayList<>();
q.offer(target);
visited.add(target.val);
while (!q.isEmpty() && K >= 0) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode curt = q.poll();
if (K == 0) res.add(curt.val);
if (map.get(curt) != null) {
for (TreeNode next : map.get(curt)) {
if (visited.contains(next.val)) continue;
visited.add(next.val);
q.offer(next);
}
}
}
K--;
}
return res;
}
private void traverse(TreeNode curt, TreeNode parent, Map<TreeNode, Set<TreeNode>> map) {
if (curt == null) return;
map.putIfAbsent(curt, new HashSet<>());
map.putIfAbsent(parent, new HashSet<>());
if (parent != null) {
map.get(curt).add(parent);
map.get(parent).add(curt);
}
traverse(curt.left, curt, map);
traverse(curt.right, curt, map);
}
Count left and right children's nodes of the player 1's initial node with value x
. Lets call countLeft
and countRight
.
count
will recursively count the number of nodes,
in the left and in the right.
n - countLeft - countRight
will be the number of nodes in the "subtree" of parent.
Now we just need to compare max(left, right, parent)
and n / 2
int countLeft = 0, countRight = 0;
public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
int count = count(root, x);
return Math.max(Math.max(countLeft, countRight),
n - countLeft - countRight - 1) > n / 2;
}
private int count(TreeNode root, int x) {
if (root == null) {
return 0;
}
int L = count(root.left, x);
int R = count(root.right, x);
if (root.val == x) {
countLeft = L;
countRight = R;
}
return L + R + 1;
}
long res = Long.MAX_VALUE;
int min;
public int findSecondMinimumValue(TreeNode root) {
min = root.val;
dfs(root);
return res == Long.MAX_VALUE ? -1 : (int)res;
}
private void dfs(TreeNode root) {
if (root == null) return;
if (root.val < res && root.val > min) {
res = root.val;
}
dfs(root.left);
dfs(root.right);
}
Last updated
Was this helpful?