二叉樹作為經典面試系列，那么當然要來看看。總計14道題，包含大量的簡單題，說明這確實是個比較基礎的專題。快速過快速過。
先構造一個二叉樹數據結構。
public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) {this.val = val;}TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}public static TreeNode build(List<Integer> nodes) {if (nodes == null || nodes.isEmpty()) {return null;}List<TreeNode> treeList = new ArrayList<>();int nodePos = 0;int nodeLen = nodes.size();TreeNode root = new TreeNode(nodes.get(nodePos++));treeList.add(root);int treePos = 0;int treeLen = treeList.size();while (treePos < treeLen && nodePos < nodeLen) {TreeNode nowNode = treeList.get(treePos++);Integer nowVal = nodes.get(nodePos++);if (nowVal != null) {TreeNode leftNode = new TreeNode(nowVal);treeList.add(leftNode);nowNode.left = leftNode;}if (nodePos < nodeLen) {nowVal = nodes.get(nodePos++);if (nowVal != null) {TreeNode rightNode = new TreeNode(nowVal);treeList.add(rightNode);nowNode.right = rightNode;}}treeLen = treeList.size();}return root;}private List<Integer> levelOrderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();List<TreeNode> treeQueue = new ArrayList<>();if (root == null) {return Collections.emptyList();}treeQueue.add(root);int len = treeQueue.size();int pos = 0;int actualLen = len;while (pos < len) {for (int i = pos; i < len; i++) {TreeNode treeNode = treeQueue.get(i);if (treeNode == null) {if (i < actualLen) {result.add(null);}continue;}result.add(treeNode.val);treeQueue.add(treeNode.left);if (treeNode.left != null) {actualLen = treeQueue.size();}treeQueue.add(treeNode.right);if (treeNode.right != null) {actualLen = treeQueue.size();}len = treeQueue.size();}pos = len;}return result;}@Overridepublic String toString() {return levelOrderTraversal(this).toString();}
}94. Binary Tree Inorder Traversal[Easy]
思路：中序遍歷，沒啥說的了，直接過
class Solution {public List<Integer> inorderTraversal(TreeNode root) {if (root == null) {return new ArrayList<>();}List<Integer> result = new ArrayList<>();result.addAll(inorderTraversal(root.left));result.add(root.val);result.addAll(inorderTraversal(root.right));return result;}
}98. Validate Binary Search Tree[Medium]
思路：驗證二叉搜索樹，?完全可以用上面編號102題層序遍歷上面編號94題中序遍歷的代碼，最后判斷一下中序遍歷的結果是否遞增即可
class Solution {public boolean isValidBST(TreeNode root) {List<Integer> inorderTraversal = inorderTraversal(root);int len = inorderTraversal.size();for (int i = 1; i < len; i++) {if (inorderTraversal.get(i) <= inorderTraversal.get(i - 1)) {return false;}}return true;}
}當然，用前一題的思路中序遍歷一下，然后再用一個變量來記錄當前遍歷的數值，可以完成優化
class Solution {private Integer current;public boolean isValidBST(TreeNode root) {if (root.left != null && !isValidBST(root.left)) {return false;}if (current != null && current >= root.val) {return false;}current = root.val;if (root.right != null && !isValidBST(root.right)) {return false;}return true;}
}101. Symmetric Tree[Easy]
思路：判斷二叉樹是否對稱。最近寫回溯寫多了，不過這不是個回溯，這就是個正向遞歸，遞歸左右子樹判斷是否對稱即可
class Solution {public boolean isSymmetric(TreeNode root) {if (root == null) {return true;}return isSymmetric(root.left, root.right);}public boolean isSymmetric(TreeNode leftTree, TreeNode rightTree) {if (leftTree == null && rightTree == null) {return true;}if (!(leftTree != null && rightTree != null)) {return false;}if (leftTree.val != rightTree.val) {return false;}if (!isSymmetric(leftTree.left, rightTree.right)) {return false;}if (!isSymmetric(leftTree.right, rightTree.left)) {return false;}return true;}
}102. Binary Tree Level Order Traversal[Medium]
思路：二叉樹層序遍歷，沒啥好說的，直接模擬隊列即可
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<TreeNode> treeQueue = new ArrayList<>();List<List<Integer>> result = new ArrayList<>();if (root == null) {return result;}treeQueue.add(root);int len = treeQueue.size();int pos = 0;while (pos < len) {List<Integer> levelResult = new ArrayList<>();for (int i = pos; i < len; i++) {TreeNode treeNode = treeQueue.get(i);levelResult.add(treeNode.val);if (treeNode.left != null) {treeQueue.add(treeNode.left);}if (treeNode.right != null) {treeQueue.add(treeNode.right);}}pos = len;len = treeQueue.size();result.add(levelResult);}return result;}
}104. Maximum Depth of Binary Tree[Easy]
思路：求樹的最大深度，這就是遞歸求左右子樹最大深度然后對比即可，真一行代碼搞定
class Solution {public int maxDepth(TreeNode root) {return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;}
}105. Construct Binary Tree from Preorder and Inorder Traversal[Medium]
思路：根據前序遍歷和中序遍歷構造二叉樹，這又是一道再經典不過的題了。前序遍歷用于尋找父節點，推動遍歷子樹；中序遍歷則用于劃分左右子樹。
class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {Map<Integer, Integer> inorderMap = new HashMap<>();int len = inorder.length;for (int i = 0; i < len; i++) {inorderMap.put(inorder[i], i);}return buildTree(preorder, inorder, 0, len, 0, len, inorderMap);}private TreeNode buildTree(int[] preorder, int[] inorder, int preStartPos, int preEndPos, int inStartPos,int inEndPos, Map<Integer, Integer> inorderMap) {int root = preorder[preStartPos];if (preStartPos == preEndPos) {return new TreeNode(root);}int inRootPos = inorderMap.get(root);int leftLen = inRootPos - inStartPos;TreeNode leftTree = buildTree(preorder, inorder, preStartPos + 1, preStartPos + leftLen, inStartPos, inRootPos,inorderMap);TreeNode rightTree = buildTree(preorder, inorder, preStartPos + leftLen + 1, preEndPos, inRootPos + 1, inEndPos,inorderMap);return new TreeNode(root, leftTree, rightTree);}
}108. Convert Sorted Array to Binary Search Tree[Easy]
思路：別看easy題就放飛自我了。將有序數組轉換為二叉搜索樹，不僅保證樹平衡，也要保證每個子樹平衡，因此也要用到遞歸的
class Solution {public TreeNode sortedArrayToBST(int[] nums) {return sortedArrayToBST(nums, 0, nums.length);}private TreeNode sortedArrayToBST(int[] nums, int begin, int end) {if (begin >= end) {return null;}int mid = (begin + end) / 2;TreeNode root = new TreeNode(nums[mid]);TreeNode leftTree = sortedArrayToBST(nums, begin, mid);TreeNode rightTree = sortedArrayToBST(nums, mid + 1, end);root.left = leftTree;root.right = rightTree;return root;}
}114. Flatten Binary Tree to Linked List[Medium]
思路：將二叉樹壓成鏈。這就涉及到二叉樹斷鏈和合鏈操作了。想清楚寫個遞歸即可
class Solution {public void flatten(TreeNode root) {flattenTree(root);}private TreeNode flattenTree(TreeNode root) {if (root == null) {return null;}TreeNode leftTree = flattenTree(root.left);TreeNode rightTree = flattenTree(root.right);if (leftTree != null) {root.right = leftTree;root.left = null;if (rightTree != null) {while (leftTree.right != null) {leftTree = leftTree.right;}leftTree.right = rightTree;}}return root;}
}199. Binary Tree Right Side View[Medium]
思路：求二叉樹的右視圖，這個就完全可以用上面編號102題層序遍歷的代碼，然后取每層最后一個即可
class Solution {public List<Integer> rightSideView(TreeNode root) {List<List<Integer>> levelOrder = levelOrder(root);return levelOrder.stream().map(list -> list.get(list.size() - 1)).collect(Collectors.toList());}
}當然，也可以將層序遍歷的代碼拿來優化一下，不需要記錄層序遍歷多余的節點，只需要記錄每層末節點即可
class Solution {public List<Integer> rightSideView(TreeNode root) {List<TreeNode> treeQueue = new ArrayList<>();List<Integer> result = new ArrayList<>();if (root == null) {return Collections.emptyList();}treeQueue.add(root);int len = treeQueue.size();int pos = 0;while (pos < len) {int lastNode = root.val;for (int i = pos; i < len; i++) {TreeNode treeNode = treeQueue.get(i);lastNode = treeNode.val;if (treeNode.left != null) {treeQueue.add(treeNode.left);}if (treeNode.right != null) {treeQueue.add(treeNode.right);}}pos = len;len = treeQueue.size();result.add(lastNode);}return result;}
}230. Kth Smallest Element in a BST[Medium]
思路：求二叉搜索樹的第k小值，又可以用到上面編號94題中序遍歷的代碼，然后取遍歷數組中的第k個即可
class Solution {public int kthSmallest(TreeNode root, int k) {List<Integer> inorderTraversal = inorderTraversal(root);return inorderTraversal.get(k - 1);}
}當然，與上一題同樣的原理，優化一下，用一個變量來記錄一下當前遍歷到的位置，這樣就可以在搜索到結果的時候提前結束，降低時耗
class Solution {private int now = 1;public int kthSmallest(TreeNode root, int k) {if (root == null) {return -1;}int leftValue = kthSmallest(root.left, k);if (leftValue != -1) {return leftValue;}if (now == k) {return root.val;}now++;return kthSmallest(root.right, k);}
}437. Path Sum III[Medium]
思路：求二叉樹中路徑和為特定樹的路徑個數。這一題有一點點樹上DP的感覺，每個節點分別往左右子樹上遞歸，分為計算該節點和不計算該結點進行轉移。最后注意一個小細節，就是要注意邊界問題，多個數的和是很可能超int邊界的，注意要開成long
class Solution {public int pathSum(TreeNode root, int targetSum) {return pathSum(root, targetSum, true) + pathSum(root, targetSum, false);}private int pathSum(TreeNode root, long targetSum, boolean include) {int count = 0;if (root == null) {return count;}if (include) {if (root.val == targetSum) {count++;}count += pathSum(root.left, targetSum - root.val, true);count += pathSum(root.right, targetSum - root.val, true);} else {count += pathSum(root.left, targetSum, true);count += pathSum(root.right, targetSum, true);count += pathSum(root.left, targetSum, false);count += pathSum(root.right, targetSum, false);}return count;}
}求和問題，當然再來一套前綴和。經典的字符串前綴和可以看我之前的哈希系列
class Solution {public int pathSum(TreeNode root, int targetSum) {HashMap<Long, Integer> sumMap = new HashMap<>();sumMap.put(0L, 1);return preSumPre(root, targetSum, sumMap, 0);}private int preSumPre(TreeNode root, int targetSum, Map<Long, Integer> sumMap, long currentSum) {int count = 0;if (root == null) {return count;}currentSum += root.val;if (sumMap.containsKey(currentSum - targetSum)) {count += sumMap.get(currentSum - targetSum);}sumMap.put(currentSum, sumMap.getOrDefault(currentSum, 0) + 1);count += preSumPre(root.left, targetSum, sumMap, currentSum);count += preSumPre(root.right, targetSum, sumMap, currentSum);sumMap.put(currentSum, sumMap.getOrDefault(currentSum, 0) - 1);return count;}
}543. Diameter of Binary Tree[Easy]
思路：求二叉樹最長路徑。首先要遞歸求每個子樹的最長路徑，即等于左右子樹的高度和。遞歸函數將子樹高度返回，用一個單獨的變量記錄當前最長路徑并在每個子樹內比較更新即可
class Solution {private int maxLength = 0;public int diameterOfBinaryTree(TreeNode root) {getLength(root);return maxLength;}private int getLength(TreeNode root) {if (root == null) {return 0;}int leftLength = getLength(root.left);int rightLength = getLength(root.right);if (leftLength + rightLength > maxLength) {maxLength = leftLength + rightLength;}return Math.max(leftLength, rightLength) + 1;}
}236. Lowest Common Ancestor of a Binary Tree[Medium]
這就是前兩天剛做過的通義app面試題，關于LCA的問題我專門特地整理了一下，感興趣可以前去看看：
最近公共祖先（LCA）
226. Invert Binary Tree[Easy]
偶然發現，這題我在五年前校招刷題的時候也寫過，當時的鏈接：二叉樹翻轉鏈接
左右子樹遞歸交換一下即可
class Solution {public TreeNode invertTree(TreeNode root) {if (root == null) {return null;}TreeNode left = invertTree(root.left);TreeNode right = invertTree(root.right);root.left = right;root.right = left;return root;}
}再來看一下當時我這題，我把他和另兩道鏈表的題總結在了一起，剛好這個二叉樹專題就要結束了，順便預告溫習一下百題斬的下一個專題，就是鏈表專題
最后，完結撒花，下個專題再見
?
 overlay)
