二叉树系列算法题
给定三个参数，二叉树的头节点head，树上某个节点target，正数K。从target开始，可以向上走或者向下走，返回与target的距离是K的所有节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| public class solution {
static class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
}
public static HashMap<Node, Node> buildParentMap(Node head) {
HashMap<Node, Node> parentMap = new HashMap<>();
Queue<Node> queue = new LinkedList<>();
queue.add(head);
while (!queue.isEmpty()) {
Node top = queue.poll();
if (top.left != null) {
parentMap.put(top.left, top);
queue.add(top.left);
}
if (top.right != null) {
parentMap.put(top.right, top);
queue.add(top.right);
}
}
return parentMap;
}
public static List<Node> distinctKNodes(Node head, Node target, int K) {
HashMap<Node, Node> parentMap = buildParentMap(head);
HashSet<Node> visited = new HashSet<>();
Queue<Node> queue = new LinkedList<>();
queue.add(target);
visited.add(target);
for (int i = 0; i < K; i++) {
List<Node> turn = new ArrayList<>();
while (!queue.isEmpty()) {
Node top = queue.poll();
if (top.left != null && !visited.contains(top.left)) {
turn.add(top.left);
visited.add(top.left);
}
if (top.right != null && !visited.contains(top.right)) {
turn.add(top.right);
visited.add(top.right);
}
if (parentMap.containsKey(top) && !visited.contains(parentMap.get(top))) {
turn.add(parentMap.get(top));
visited.add(parentMap.get(top));
}
}
queue.addAll(turn);
}
return queue.stream().toList();
}
}
|
已知一棵搜索二叉树上没有重复值的节点，现在有一个数组arr，是这棵搜索二叉树先序遍历的结果，请根据arr生成整棵树并返回头节点
https://leetcode-cn.com/problems/construct-binary-search-tree-from-preorder-traversal/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| class Solution {
public TreeNode bstFromPreorder(int[] arr) {
return generateTree(arr, 0, arr.length-1);
}
public TreeNode generateTree(int[] arr, int start, int end) {
if (arr == null || arr.length < end + 1 || start > end) {
return null;
}
if (start == end) {
return new TreeNode(arr[start]);
}
TreeNode head = new TreeNode(arr[start]);
int N = arr.length;
int leftIndex = 0;
int rightIndex = 0;
int i = start + 1;
while (i <= end) {
if (arr[i] < arr[start] && leftIndex == 0) {
leftIndex = i;
} else if (arr[i] > arr[start]) {
rightIndex = i;
break;
}
i ++;
}
if (leftIndex != 0) {
head.left = generateTree(arr, leftIndex, rightIndex != 0 ? rightIndex-1 : end);
}
if (rightIndex != 0) {
head.right = generateTree(arr, rightIndex, end);
}
return head;
}
}
|
优化generateTree方法（简洁，但不好理解）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public TreeNode generateTree(int[] arr, int start, int end) {
if (start > end) {
return null;
}
TreeNode head = new TreeNode(arr[start]);
int N = arr.length;
int rightIndex = start + 1;
for (; rightIndex <= end; rightIndex++) {
if (arr[rightIndex] > arr[start]) {
break;
}
}
head.left = generateTree(arr, start+1, rightIndex-1);
head.right = generateTree(arr, rightIndex, end);
return head;
}
|
如果一个节点X，它左树结构和右树结构完全一样，那么我们说以X为头的树是相等树，给定一棵二叉树的头节点head，返回head整棵树上有多少棵相等子树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| public int theSameTreeNum(Node head) {
if (head == null) {
return 0;
}
Queue<Node> queue = new LinkedList<>();
queue.add(head);
Map<Node, Boolean> sameTreeHeadMap = new HashMap<>();
int sameTreeHeadNum = 0;
while (!queue.isEmpty()) {
Node top = queue.poll();
if (top.left != null) {
queue.add(top.left);
}
if (top.right != null) {
queue.add(top.right);
}
if (theSameTreeNode(top.left, top.right)) {
sameTreeHeadNum ++;
}
}
return sameTreeHeadNum;
}
public int theSameTreeNum2(Node head) {
if (head == null) {
return 0;
}
return theSameTreeNum2(head.left) + theSameTreeNum2(head.right) + (theSameTreeNode(head.left, head.right) ? 1 : 0);
}
public boolean theSameTreeNode(Node n1, Node n2) {
if (n1 == null ^ n2 == null) {
return false;
}
if (n1 == null && n2 == null) {
return true;
}
return theSameTreeNode(n1.left, n2.left) && theSameTreeNode(n1.right, n2.right) && n1.value == n2.value;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return compare(root.left, root.right);
}
private boolean compare(TreeNode node1, TreeNode node2) {
if (node1 != null && node2 != null) {
return node1.val == node2.val && compare(node1.left, node2.right)
&& compare(node1.right, node2.left);
}
return node1 == node2;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left != null || root.right != null) {
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
return 1;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
int[] minDepth = {Integer.MAX_VALUE};
dfs(root, 1, minDepth);
return minDepth[0];
}
private void dfs(TreeNode node, int depth, int[] minDepth) {
if (node == null) {
return;
}
if (depth >= minDepth[0]) {
return;
}
if (node.left == null && node.right == null) {
minDepth[0] = depth;
}
depth ++;
dfs(node.left, depth, minDepth);
dfs(node.right, depth, minDepth);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
TreeNode left = root.left;
TreeNode right = root.right;
int leftHeight = 0;
int rightHeight = 0;
while (left != null) {
left = left.left;
leftHeight ++;
}
while (right != null) {
right = right.right;
rightHeight ++;
}
if (leftHeight == rightHeight) {
return (2 << leftHeight) - 1;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
if (Math.abs(leftHeight - rightHeight) > 1) {
return false;
}
return isBalanced(root.left) && isBalanced(root.right);
}
private int getHeight(TreeNode node) {
if (node == null) {
return 0;
}
return Math.max(getHeight(node.left), getHeight(node.right)) + 1;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public boolean isValidBST(TreeNode root) {
return travel(root, Long.MAX_VALUE, Long.MIN_VALUE);
}
private boolean travel(TreeNode node, long max, long min) {
if (node == null) {
return true;
}
if (node.val >= max || node.val <= min) {
return false;
}
return travel(node.left, node.val, min) && travel(node.right, max, node.val);
}
}
|
给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。
如果节点不存在，则返回 null
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if (root == null) {
return null;
}
if (root.val == val) {
return root;
}
if (root.val > val) {
return searchBST(root.left, val);
}
return searchBST(root.right, val);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null) {
return root2;
}
if (root2 == null) {
return root1;
}
root1.val += root2.val;
root1.left = mergeTrees(root1.left, root2.left);
root1.right = mergeTrees(root1.right, root2.right);
return root1;
}
}
|
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums
递归地构建:
创建一个根节点，其值为 nums 中的最大值。 递归地在最大值 左边 的
子数组前缀上 构建左子树。 递归地在最大值 右边 的 子数组后缀上
构建右子树。 返回 nums 构建的 最大二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
if (nums == null || nums.length == 0) {
return null;
}
int max = Integer.MIN_VALUE;
int maxPosition = -1;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > max) {
max = nums[i];
maxPosition = i;
}
}
TreeNode root = new TreeNode(max);
int[] leftNums = new int[maxPosition];
for (int i = 0; i < maxPosition; i++) {
leftNums[i] = nums[i];
}
int[] rightNums = new int[nums.length - maxPosition - 1];
for (int i = maxPosition + 1; i < nums.length; i++) {
rightNums[i - maxPosition - 1] = nums[i];
}
root.left = constructMaximumBinaryTree(leftNums);
root.right = constructMaximumBinaryTree(rightNums);
return root;
}
}
|
注：可以通过控制数组下标进行优化，不要拷贝数组，而是控制要处理的下标范围
给定两个整数数组 inorder 和 postorder ，其中 inorder
是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗
二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder == null || inorder.length == 0 || postorder == null || postorder.length == 0) {
return null;
}
TreeNode root = new TreeNode(postorder[postorder.length - 1]);
int position = 0;
for (int i = 0; i < inorder.length; i++) {
if (inorder[i] == root.val) {
position = i;
break;
}
}
int[] leftInOrder = new int[position];
int[] rightInOrder = new int[inorder.length - position - 1];
for (int i = 0; i < position; i++) {
leftInOrder[i] = inorder[i];
}
for (int i = position + 1; i < inorder.length; i++) {
rightInOrder[i - position - 1] = inorder[i];
}
int[] leftPostOrder = new int[position];
int[] rightPostOrder = new int[postorder.length - position - 1];
for (int i = 0; i < position; i++) {
leftPostOrder[i] = postorder[i];
}
for (int i = position; i < postorder.length - 1; i++) {
rightPostOrder[i - position] = postorder[i];
}
root.left = buildTree(leftInOrder, leftPostOrder);
root.right = buildTree(rightInOrder, rightPostOrder);
return root;
}
}
|
注：可以通过控制数组下标进行优化，不要拷贝数组，而是控制要处理的下标范围
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum
。判断该树中是否存在 根节点到叶子节点
的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回
true ；否则，返回 false
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
if (root.left == null && root.right == null) {
return root.val == targetSum;
}
return hasPathSum(root.left, targetSum - root.val) ||
hasPathSum(root.right, targetSum - root.val);
}
}
|
难度中等284收藏分享切换为英文接收动态反馈
给定一个二叉树的 根节点
root，请找出该二叉树的 最底层 最左边
节点的值。
假设二叉树中至少有一个节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public int findBottomLeftValue(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
TreeNode leftLastLeaf = root;
while (!queue.isEmpty()) {
List<TreeNode> nextFloor = new ArrayList<>();
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node.left != null) {
nextFloor.add(node.left);
}
if (node.right != null) {
nextFloor.add(node.right);
}
}
if (!nextFloor.isEmpty()) {
leftLastLeaf = nextFloor.get(0);
queue.addAll(nextFloor);
} else {
return leftLastLeaf.val;
}
}
return 0;
}
}
|
难度简单463收藏分享切换为英文接收动态反馈
给定二叉树的根节点 root ，返回所有左叶子之和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) {
return 0;
}
return travel(root.left, true) + travel(root.right, false);
}
private int travel(TreeNode node, Boolean leftTurn) {
if (node == null) {
return 0;
}
if (node.left == null && node.right == null) {
if (leftTurn) {
return node.val;
}
return 0;
}
return travel(node.left, true) + travel(node.right, false);
}
}
|
难度简单751收藏分享切换为英文接收动态反馈
给你一个二叉树的根节点 root ，按
任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> paths = new ArrayList<>();
if (root == null) {
return paths;
}
if (root.left == null && root.right == null) {
paths.add(root.val + "");
return paths;
}
List<String> leftPaths = binaryTreePaths(root.left);
List<String> rightPaths = binaryTreePaths(root.right);
for (String p : leftPaths) {
paths.add(root.val + "->" + p);
}
for (String p : rightPaths) {
paths.add(root.val + "->" + p);
}
return paths;
}
}
|
给你一个含重复值的二叉搜索树（BST）的根节点 root
，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| class Solution {
private TreeNode preTravelNode;
private int maxModeNum = Integer.MIN_VALUE;
private int modeNum = 0;
public int[] findMode(TreeNode root) {
if (root == null) {
return new int[0];
}
List<Integer> modes = new ArrayList<>();
midTravel2(root, modes);
int[] arr = new int[modes.size()];
for (int i = 0; i < modes.size(); i++) {
arr[i] = modes.get(i);
}
return arr;
}
private void midTravel2(TreeNode node, List<Integer> modes) {
if (node == null) {
return;
}
midTravel2(node.left, modes);
if (preTravelNode != null) {
if (preTravelNode.val == node.val) {
modeNum ++;
} else {
modeNum = 1;
}
} else {
modeNum = 1;
}
if (modeNum == maxModeNum) {
modes.add(node.val);
} else if (modeNum > maxModeNum) {
modes.clear();
modes.add(node.val);
maxModeNum = modeNum;
}
preTravelNode = node;
midTravel2(node.right, modes);
}
}
|
给你一个二叉搜索树的根节点 root ，返回
树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public int getMinimumDifference(TreeNode root) {
if (root == null) {
return 0;
}
int minDistance = Integer.MAX_VALUE;
Stack<TreeNode> stack = new Stack<>();
pushStack(root, stack);
TreeNode prePopNode = null;
while (!stack.isEmpty()) {
TreeNode head = stack.pop();
if (prePopNode != null) {
minDistance = Math.min(minDistance, head.val - prePopNode.val);
}
prePopNode = head;
if (head.right != null) {
pushStack(head.right, stack);
}
}
return minDistance;
}
private void pushStack(TreeNode node, Stack<TreeNode> stack) {
while (node != null) {
stack.push(node);
node = node.left;
}
}
}
|
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 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) {
return right;
}
if (right == null) {
return left;
}
return root;
}
}
|
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先
1
2
3
4
5
6
7
8
9
10
| class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root.val > p.val && root.val > q.val) {
return lowestCommonAncestor(root.left, p, q);
} else if (root.val < p.val && root.val < q.val) {
return lowestCommonAncestor(root.right, p, q);
}
return root;
}
}
|
给定二叉搜索树（BST）的根节点 root 和要插入树中的值
value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。
输入数据 保证
，新值和原始二叉搜索树中的任意节点值都不同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}
TreeNode node = root;
TreeNode preNode = root;
while (node != null) {
preNode = node;
if (node.val > val) {
node = node.left;
} else {
node = node.right;
}
}
if (preNode.val > val) {
preNode.left = new TreeNode(val);
} else {
preNode.right = new TreeNode(val);
}
return root;
}
}
|
给定一个二叉搜索树的根节点 root 和一个值
key，删除二叉搜索树中的 key
对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return null;
}
if (root.val == key) {
if (root.left == null && root.right == null) {
return null;
}
if (root.left == null) {
return root.right;
}
if (root.right == null) {
return root.left;
}
TreeNode node = root.left;
while (node.right != null) {
node = node.right;
}
node.right = root.right;
return root.left;
}
if (root.val > key) {
root.left = deleteNode(root.left, key);
} else {
root.right = deleteNode(root.right, key);
}
return root;
}
}
|
注：情况5较难考虑
给你二叉搜索树的根节点 root
，同时给定最小边界low 和最大边界
high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树
不应该 改变保留在树中的元素的相对结构
(即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在
唯一的答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
if (root == null) {
return null;
}
if (root.val < low) {
return trimBST(root.right, low, high);
}
if (root.val > high) {
return trimBST(root.left, low, high);
}
root.left = trimBST(root.left, low, high);
root.right = trimBST(root.right, low, high);
return root;
}
}
|
给你一个整数数组 nums ，其中元素已经按
升序 排列，请你将其转换为一棵 高度平衡
二叉搜索树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if (nums == null || nums.length == 0) {
return null;
}
return travel(nums, 0, nums.length-1);
}
private TreeNode travel(int[] nums, int left, int right) {
if (left > right) {
return null;
}
int mid = left + (right - left) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = travel(nums, left, mid-1);
root.right = travel(nums, mid + 1, right);
return root;
}
}
|
给出二叉 搜索
树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum
Tree），使每个节点 node 的新值等于原树中大于或等于
node.val 的值之和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
private TreeNode preNode = new TreeNode(0);
public TreeNode convertBST(TreeNode root) {
if (root == null) {
return null;
}
convertBST(root.right);
root.val += preNode.val;
preNode = root;
convertBST(root.left);
return root;
}
}
|
总结
- 二叉树递归过程中，可能需要用到额外的类属性记录过程值
- 递归可以用栈代替
二叉树总结