Leetcode百题斩-二叉树

二叉树作为经典面试系列，那么当然要来看看。总计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;}
}

再来看一下当时我这题，我把他和另两道链表的题总结在了一起，刚好这个二叉树专题就要结束了，顺便预告温习一下百题斩的下一个专题，就是链表专题

最后，完结撒花，下个专题再见

​