# General ## 104 Max depth public int maxDepth(TreeNode root) { if(root == null) return 0; ``` return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; ``` } ## 111 Min depth ```java public int minDepth(TreeNode root) { if(root == null) return 0; if(root.left == null) return minDepth(root.right) + 1; if(root.right == null) return minDepth(root.left) + 1; return Math.min(minDepth(root.left), minDepth(root.right)) + 1; } ``` ## 110 Check Balanced a binary tree in which the depth of the two subtrees of every node never differ by more than 1. ```java public boolean isBalanced(TreeNode root) { return maxDepth(root) == -1 ? false : true; } private int maxDepth(TreeNode root){ if(root == null) return 0; int left = maxDepth(root.left); int right = maxDepth(root.right); if(left == -1 || right == -1 || Math.abs(left-right) > 1) return -1; return Math.max(left, right) + 1; } ``` ## 285 Inorder Successor/Predecessor in BST Given a binary search tree and a node in it, find the in-order successor of that node in the BST. Note: If the given node has no in-order successor in the tree, return null. ![](/files/-LrHBSjcJ6ZCi6QNdzPR) * Successor ```java public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { if(root == null) return null; if(root.val <= p.val) return inorderSuccessor(root.right, p); else{ TreeNode left = inorderSuccessor(root.left, p); return left == null ? root : left; } } ``` * Predecessor ```java public TreeNode predecessor(TreeNode root, TreeNode p){ if(root == null) return null; if(root.val >= p.val) return predecessor(root.left, p); else{ TreeNode right= predecessor(root.right, p); return right==null? node : right; } } ``` ## 654 Maximum Binary Tree Given an integer array with no duplicates. A maximum tree building on this array is defined as follow: 1. The root is the maximum number in the array. 2. The left subtree is the maximum tree constructed from left part subarray divided by the maximum number. 3. 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) ```java 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 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) ```java 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) ```java 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. ![](/files/-M2yeTIMj1E_0eVxf8jM) ```python """ 分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 ```python 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 ``` --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://netjimmy.gitbook.io/code-interview-note/binary_tree/general.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.