Skip to content

Commit 48ec2a4

Browse files
leosanqingleosanqing
committed
1. 新增部分题目
1 parent 60d4140 commit 48ec2a4

10 files changed

Lines changed: 473 additions & 29 deletions

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/easy/tree/_107_binary_tree_level_order_traversalII.java‎

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
package com.leosanqing.leetcode.easy.tree;
2+
3+
import com.leosanqing.leetcode.medium.tree.TreeNode;
4+
5+
import java.util.ArrayList;
6+
import java.util.Collections;
7+
import java.util.List;
8+
9+
/**
10+
* @Author: rtliu
11+
* @Date: 2020/7/29 下午4:15
12+
* @Package: com.leosanqing.leetcode.easy.tree
13+
* @Description: 1
14+
* ` Given a binary tree, return the bottom-up level order traversal of its nodes' values.
15+
* ` (ie, from left to right, level by level from leaf to root).
16+
* ` For example: Given binary tree [3,9,20,null,null,15,7],
17+
* ` 3
18+
* ` / \
19+
* ` 9 20
20+
* ` / \
21+
* ` 15 7
22+
* ` return its bottom-up level order traversal as:
23+
* ` [
24+
* ` [15,7],
25+
* ` [9,20],
26+
* ` [3]
27+
* ` ]
28+
* @Version: 1.0
29+
*/
30+
public class _107_binary_tree_level_order_traversalII {
31+
public static void main(String[] args) {
32+
TreeNode treeNode = new TreeNode(3);
33+
treeNode.left = new TreeNode(9);
34+
treeNode.right = new TreeNode(20);
35+
treeNode.right.left = new TreeNode(15);
36+
treeNode.right.right = new TreeNode(7);
37+
levelOrderBottom(treeNode);
38+
}
39+
40+
public static List<List<Integer>> levelOrderBottom(TreeNode root) {
41+
42+
List<List<Integer>> answer = new ArrayList<>();
43+
44+
backTrace(answer, 0, root);
45+
Collections.reverse(answer);
46+
return answer;
47+
}
48+
49+
50+
private static void backTrace(List<List<Integer>> answer, int depth, TreeNode root) {
51+
if (root == null) {
52+
return;
53+
}
54+
55+
if (answer.size() > depth) {
56+
answer.get(depth).add(root.val);
57+
} else {
58+
List<Integer> list = new ArrayList<>();
59+
list.add(root.val);
60+
answer.add(new ArrayList<>(list));
61+
}
62+
63+
backTrace(answer, depth + 1, root.left);
64+
backTrace(answer, depth + 1, root.right);
65+
66+
}
67+
}

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/easy/tree/_108_convert_sorted_array_to_binary_search_tree.java‎

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
package com.leosanqing.leetcode.easy.tree;
2+
3+
import com.leosanqing.leetcode.medium.tree.TreeNode;
4+
5+
/**
6+
* @Author: rtliu
7+
* @Date: 2020/7/30 上午9:26
8+
* @Package: com.leosanqing.leetcode.easy.tree
9+
* @Description: 1
10+
* ` Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
11+
* ` For this problem,
12+
* ` a height-balanced binary tree is defined as a binary tree in
13+
* ` which the depth of the two subtrees of every node never differ by more than 1.
14+
* `
15+
* `
16+
* ` 给定一个数组，其中元素按升序排序，请将其转换为高度平衡的BST。
17+
* ` 比如这个问题，
18+
* ` 高度平衡的二叉树被定义为
19+
* ` 每个节点的两个子树的深度相差不超过1。
20+
* ` Example:
21+
* ` Given the sorted array: [-10,-3,0,5,9],
22+
* ` One possible answer is: [0,-3,9,-10,null,5],
23+
* ` which represents the following height balanced BST:
24+
* ` 0
25+
* ` / \
26+
* ` -3 9
27+
* ` / /
28+
* ` -10 5
29+
* @Version: 1.0
30+
*/
31+
public class _108_convert_sorted_array_to_binary_search_tree {
32+
33+
34+
public static TreeNode sortedArrayToBST(int[] nums) {
35+
return backTrace(nums,0,nums.length-1);
36+
}
37+
38+
private static TreeNode backTrace(int[] nums, int left, int right) {
39+
if (left > right) {
40+
return null;
41+
}
42+
43+
int mid = (right - left) / 2 + left;
44+
45+
TreeNode root = new TreeNode(nums[mid]);
46+
47+
root.left = backTrace(nums, left, mid - 1);
48+
root.right = backTrace(nums, mid + 1, right);
49+
return root;
50+
}
51+
52+
53+
}

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/easy/tree/_110_balanced_binary_tree.java‎

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
package com.leosanqing.leetcode.easy.tree;
2+
3+
import com.leosanqing.leetcode.medium.tree.TreeNode;
4+
5+
/**
6+
* @Author: rtliu
7+
* @Date: 2020/7/30 下午3:06
8+
* @Package: com.leosanqing.leetcode.easy.tree
9+
* @Description: 1
10+
* ` Given a binary tree, determine if it is height-balanced.
11+
* ` For this problem, a height-balanced binary tree is defined as:
12+
* ` a binary tree in which the left and right subtrees of every node differ in height by no more than 1.
13+
* ` Example 1:
14+
* ` Given the following tree [3,9,20,null,null,15,7]:
15+
* ` 3
16+
* ` / \
17+
* ` 9 20
18+
* ` / \
19+
* ` 15 7
20+
* ` Return true.
21+
* ` Example 2:
22+
* ` Given the following tree [1,2,2,3,3,null,null,4,4]:
23+
* ` 1
24+
* ` / \
25+
* ` 2 2
26+
* ` / \
27+
* ` 3 3
28+
* ` / \
29+
* ` 4 4
30+
* @Version: 1.0
31+
*/
32+
public class _110_balanced_binary_tree {
33+
34+
private static boolean result = true;
35+
public static void main(String[] args) {
36+
TreeNode treeNode = new TreeNode(1);
37+
treeNode.left = new TreeNode(2);
38+
treeNode.right = new TreeNode(2);
39+
treeNode.left.left = new TreeNode(3);
40+
treeNode.left.right = new TreeNode(3);
41+
treeNode.right.left = new TreeNode(3);
42+
treeNode.right.right = new TreeNode(3);
43+
treeNode.left.left.left = new TreeNode(4);
44+
treeNode.left.left.right = new TreeNode(4);
45+
treeNode.left.right.left = new TreeNode(4);
46+
treeNode.left.right.right = new TreeNode(4);
47+
treeNode.right.left.left = new TreeNode(4);
48+
treeNode.right.left.right = new TreeNode(4);
49+
treeNode.left.left.left.left = new TreeNode(4);
50+
treeNode.left.left.left.right = new TreeNode(4);
51+
System.out.println(isBalanced(treeNode));
52+
}
53+
public static boolean isBalanced(TreeNode root) {
54+
result = true;
55+
backTrace(root);
56+
return result;
57+
}
58+
59+
private static int backTrace(TreeNode root) {
60+
if (root == null) {
61+
return 0;
62+
}
63+
int left = backTrace(root.left);
64+
int right = backTrace(root.right);
65+
66+
if(Math.abs(left-right)>1){
67+
result = false;
68+
}
69+
70+
return 1+Math.max(left,right);
71+
}
72+
}

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/easy/tree/_111_minimum_depth_of_binary_tree.java‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
package com.leosanqing.leetcode.easy.tree;
2+
3+
import com.leosanqing.leetcode.medium.tree.TreeNode;
4+
5+
/**
6+
* @Author: rtliu
7+
* @Date: 2020/7/30 下午3:53
8+
* @Package: com.leosanqing.leetcode.easy.tree
9+
* @Description: 1
10+
* ` Given a binary tree, find its minimum depth.
11+
* ` The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
12+
* ` Note: A leaf is a node with no children.
13+
* ` Example:
14+
* ` Given binary tree [3,9,20,null,null,15,7],
15+
* ` 3
16+
* ` / \
17+
* ` 9 20
18+
* ` / \
19+
* ` 15 7
20+
* ` return its minimum depth = 2.
21+
* @Version: 1.0
22+
*/
23+
public class _111_minimum_depth_of_binary_tree {
24+
25+
26+
public int minDepth(TreeNode root) {
27+
if(root == null) {
28+
return 0;
29+
}
30+
if(root.left == null || root.right == null) {
31+
return 1 + Math.max(minDepth(root.left), minDepth(root.right));
32+
}
33+
return 1 + Math.min(minDepth(root.left), minDepth(root.right));
34+
}
35+
}

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/medium/tree/_102_binary_tree_level_order_traversal.java‎

Lines changed: 19 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,7 @@
22

33
import java.util.ArrayList;
44
import java.util.Arrays;
5+
import java.util.Collections;
56
import java.util.List;
67

78
/**
@@ -36,39 +37,28 @@ public static void main(String[] args) {
3637
}
3738

3839
public static List<List<Integer>> levelOrder(TreeNode root) {
39-
if (root == null) {
40-
return new ArrayList<>();
41-
}
42-
List<List<TreeNode>> answer = new ArrayList<>();
43-
answer.add(Arrays.asList(root));
44-
45-
List<List<Integer>> res = new ArrayList<>();
46-
res.add(Arrays.asList(root.val));
47-
findAnswer(answer, new ArrayList<>(),res,new ArrayList<>());
48-
return res;
40+
List<List<Integer>> answer = new ArrayList<>();
4941

42+
backTrace(answer, 0, root);
43+
return answer;
5044
}
5145

52-
private static void findAnswer(List<List<TreeNode>> lists, List<TreeNode> list,List<List<Integer>> answer, List<Integer> temp) {
53-
while (true) {
54-
for (TreeNode treeNode : lists.get(lists.size() - 1)) {
55-
if(treeNode.left != null){
56-
list.add(treeNode.left);
57-
temp.add(treeNode.left.val);
58-
}
59-
if(treeNode.right != null) {
60-
list.add(treeNode.right);
61-
temp.add(treeNode.right.val);
62-
}
63-
}
64-
if (list.isEmpty()) {
65-
return;
66-
}
67-
lists.add(new ArrayList<>(list));
68-
answer.add(new ArrayList<>(temp));
69-
list.clear();
70-
temp.clear();
7146

47+
private static void backTrace(List<List<Integer>> answer, int depth, TreeNode root) {
48+
if (root == null) {
49+
return;
50+
}
51+
52+
if (answer.size() > depth) {
53+
answer.get(depth).add(root.val);
54+
} else {
55+
List<Integer> list = new ArrayList<>();
56+
list.add(root.val);
57+
answer.add(new ArrayList<>(list));
7258
}
59+
60+
backTrace(answer, depth + 1, root.left);
61+
backTrace(answer, depth + 1, root.right);
62+
7363
}
7464
}

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/medium/tree/_105_construct_binary_tree_from_preorder_and_inorder_traversal.java‎

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
package com.leosanqing.leetcode.medium.tree;
2+
3+
/**
4+
* @Author: rtliu
5+
* @Date: 2020/7/28 下午7:29
6+
* @Package: com.leosanqing.leetcode.medium.tree
7+
* @Description: 1
8+
* ` Given preorder and inorder traversal of a tree, construct the binary tree.
9+
* ` Note: You may assume that duplicates do not exist in the tree.
10+
* ` For example, given preorder = [3,9,20,15,7] inorder = [9,3,15,20,7]
11+
* ` Return the following binary tree:
12+
* `
13+
* ` 给定一棵树的前序和有序遍历，构造二叉树。
14+
* ` 注意：您可以假定树中不存在重复项。
15+
* ` 例如，给定的先序遍历 = [3,9,20,15,7] 中序遍历 = [9,3,15,20,7]
16+
* ` 3
17+
* ` / \
18+
* ` 9 20
19+
* ` / \
20+
* ` 15 7
21+
* @Version: 1.0
22+
*/
23+
public class _105_construct_binary_tree_from_preorder_and_inorder_traversal {
24+
25+
public static void main(String[] args) {
26+
int[] preorder = {3, 9, 2, 11, 14, 8, 20, 15, 16, 7, 22};
27+
int[] inorder = {11, 2, 14, 9, 8, 3, 16, 15, 20, 22, 7};
28+
29+
30+
TreeNode treeNode1 = backTrace(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
31+
32+
33+
TreeNode treeNode = buildTree(preorder, inorder);
34+
35+
36+
}
37+
38+
public static TreeNode buildTree(int[] preorder, int[] inorder) {
39+
return backTrace(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
40+
}
41+
42+
private static TreeNode backTrace(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
43+
if (preStart > preorder.length - 1 || inStart > inEnd) {
44+
return null;
45+
}
46+
47+
TreeNode root = new TreeNode(preorder[preStart]);
48+
// 找到 inOrder 中 的索引
49+
int inIndex = 0;
50+
51+
for (int i = inStart; i <= inEnd; i++) {
52+
if (root.val == inorder[i]) {
53+
inIndex = i;
54+
}
55+
}
56+
57+
root.left = backTrace(preorder, preStart + 1, preEnd, inorder, inStart, inIndex - 1);
58+
root.right = backTrace(preorder, preStart + inIndex - inStart + 1, preEnd, inorder, inIndex + 1, inEnd);
59+
return root;
60+
}
61+
}

0 commit comments

Comments
 (0)