二叉树总结

hot100

二叉树的中序遍历

题目链接：
94.二叉树的中序遍历
代码：

class Solution {
// 非递归public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();Deque<TreeNode> stack = new LinkedList<>();if (root != null) {stack.push(root);}while(!stack.isEmpty()) {TreeNode node = stack.peek();if (node != null) {stack.pop();if (node.right != null) {stack.push(node.right);}stack.push(node);stack.push(null);if (node.left != null) {stack.push(node.left);}}else {stack.pop();node = stack.peek();stack.pop();res.add(node.val);}}return res;}// 递归public void traverse(TreeNode root, List<Integer> res) {if (root == null) {return ;}traverse(root.left, res);res.add(root.val);traverse(root.right, res);}public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();traverse(root, res);return res;}
}

二叉树的最大深度

题目链接：
104.二叉树的最大深度
代码：

class Solution {public int maxDepth(TreeNode root) {if(root == null) return 0;return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;}
}

二叉树的最大深度

题目链接：
104.二叉树的最大深度
代码：

class Solution {public int maxDepth(TreeNode root) {if(root == null) return 0;return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;}
}

翻转二叉树

题目链接：
226.翻转二叉树
代码：

class Solution {public TreeNode invertTree(TreeNode root) {if (root == null) {return root;}TreeNode temp = root.left;root.left = root.right;root.right = temp;invertTree(root.left);invertTree(root.right);return root;}
}

对称二叉树

题目链接：
101.对称二叉树
代码：

class Solution {public boolean isSymmetric(TreeNode l, TreeNode r){if (l == null && r == null) return true;else if (l != null && r == null) return false;else if (l == null && r != null) return false;else if (l.val != r.val) return false;return isSymmetric(l.left,r.right) && isSymmetric(l.right, r.left);}public boolean isSymmetric(TreeNode root) {if (root == null) return false;return isSymmetric(root.left, root.right);}
}

二叉树的直径

题目链接：
543.二叉树的直径
代码：

class Solution {int ans;public int getDepth(TreeNode root) {if (root == null) {return 0;}int l = getDepth(root.left);int r = getDepth(root.right);ans = Math.max(ans, l + r + 1);return Math.max(l,r) + 1;}public int diameterOfBinaryTree(TreeNode root) {getDepth(root);return ans - 1;}
}

二叉树的层序遍历

题目链接：
102.二叉树的层序遍历
代码：

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>();Queue<TreeNode> q = new LinkedList<>();if (root != null) {q.offer(root);}while(!q.isEmpty()) {List<Integer> list = new ArrayList<>();int n = q.size();while (n > 0) {TreeNode tmp = q.poll();list.add(tmp.val);if (tmp.left != null) q.offer(tmp.left);if (tmp.right != null) q.offer(tmp.right);n--;}res.add(list);}return res;}
}

将有序数组转换为二叉搜索树

题目链接：
108.将有序数组转换为二叉搜索树
代码：

class Solution {public TreeNode sort(int[] nums, int start, int end) {if (start >= end) {return null;}if (end - start == 1) {return new TreeNode(nums[start]);}int mid = start + (end - start) / 2;TreeNode midNode = new TreeNode(nums[mid]);midNode.left = sort(nums, start, mid);midNode.right = sort(nums, mid + 1, end);return midNode;}public TreeNode sortedArrayToBST(int[] nums) {return sort(nums, 0, nums.length);}
}

验证二叉搜索树

题目链接：
98.验证二叉搜索树
代码：

class Solution {TreeNode next;public boolean isValidBST(TreeNode root) {if (root == null) {return true;}boolean left = isValidBST(root.left);if (left == false) {return false;}if (next != null && root.val <= next.val) {return false;}next = root;boolean right = isValidBST(root.right);return right;}
}

二叉搜索树中第 K 小的元素

题目链接：
230.二叉搜索树中第 K 小的元素
代码：

class Solution {public int kthSmallest(TreeNode root, int k) {Deque<TreeNode> stack = new LinkedList<>();if (root != null) {stack.push(root);}while (!stack.isEmpty()){TreeNode node = stack.peek();if (node != null) {stack.pop();if (node.right != null) {stack.push(node.right);}stack.push(node);stack.push(null);if (node.left != null) {stack.push(node.left);}}else {stack.pop();node = stack.peek();stack.pop();k --;if (k == 0) {return node.val;}}}return -1;}
}

二叉树的右视图

题目链接：
199.二叉树的右视图
代码：

class Solution {public List<Integer> rightSideView(TreeNode root) {List<Integer> res = new ArrayList<>();Queue<TreeNode> pq = new LinkedList<>();if (root == null) return res;pq.offer(root);while(! pq.isEmpty()){int n = pq.size();for (int i = 0; i < n; i ++){TreeNode tmp = pq.poll();if (i == n - 1) res.add(tmp.val);if (tmp.left != null) pq.offer(tmp.left);if (tmp.right != null) pq.offer(tmp.right);}}return res;}
}

二叉树展开为链表

题目链接：
114.二叉树展开为链表
代码：

class Solution {public void traverse(TreeNode root, List<TreeNode> res) {if (root == null) {return;}res.add(root);traverse(root.left, res);traverse(root.right, res);}public void flatten(TreeNode root) {List<TreeNode> res = new ArrayList<>();traverse(root, res);for (int i = 1; i < res.size(); i ++) {TreeNode pre = res.get(i - 1), curr = res.get(i);pre.right = curr;pre.left = null;}}
}

从前序与中序遍历序列构造二叉树

题目链接：
105.从前序与中序遍历序列构造二叉树
代码：

class Solution {public Map<Integer,Integer> map;public TreeNode findNode(int[] preorder, int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd){if (preBegin >= preEnd || inBegin >= inEnd) return null;int rootIndex = map.get(preorder[preBegin]);int leftLen = rootIndex - inBegin;TreeNode root = new TreeNode(inorder[rootIndex]);root.left = findNode(preorder,preBegin + 1, preBegin + 1 + leftLen, inorder, inBegin, rootIndex);root.right = findNode(preorder, preBegin + 1 + leftLen, preEnd, inorder, rootIndex + 1,inEnd);return root;}public TreeNode buildTree(int[] preorder, int[] inorder) {map = new HashMap<>();for (int i = 0; i < inorder.length; i ++){map.put(inorder[i],i);}return findNode(preorder, 0, preorder.length, inorder,0,inorder.length);}
}

路径总和3

题目链接：
437.路径总和3
代码：

class Solution {public int dfs(TreeNode root, Map<Long, Integer> map, long curr, int targetSum) {if (root == null) {return 0;}int res = 0;curr += root.val;res = map.getOrDefault(curr - targetSum,0);map.put(curr, map.getOrDefault(curr,0) + 1);res += dfs(root.left, map, curr, targetSum);res += dfs(root.right, map, curr, targetSum);map.put(curr, map.getOrDefault(curr,0) - 1);return res;}public int pathSum(TreeNode root, int targetSum) {Map<Long, Integer> map = new HashMap<>();map.put(0L,1);return dfs(root, map,0L, targetSum);}
}

二叉树的最近公共祖先

题目链接：
236.二叉树的最近公共祖先
代码：

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null || root == p || root == q) {return root;}TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);if (left == null && right == null) return null;if (left == null && right != null) return right;if (left != null && right == null) return left;return root;}
}

二叉树中的最大路径和

题目链接：
124.二叉树中的最大路径和
代码：

class Solution {int maxSum = Integer.MIN_VALUE;public int maxGain(TreeNode node){if (node == null) return 0;// 递归计算左右子节点的最大贡献值// 只有贡献大于0，才选择对应节点int leftGain = Math.max(maxGain(node.left),0);int rightGain = Math.max(maxGain(node.right),0);// 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值int price = node.val + leftGain + rightGain;maxSum = Math.max(maxSum,price);return node.val + Math.max(leftGain,rightGain);}public int maxPathSum(TreeNode root) {maxGain(root);return maxSum;}
}