我新建的个人博客，欢迎访问：hmilzy.github.io
513. 找树左下角的值
题目链接：找树左下角的值
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
|
class Solution {
public int findBottomLeftValue(TreeNode root) {
Deque<TreeNode> deque = new LinkedList<>();
if(root != null){
deque.add(root);
}
int result = 0;
while(!deque.isEmpty()){
int size = deque.size();
for(int i = 0;i < size;i++){
TreeNode cur = deque.poll();
if(i == 0){
result = cur.val;
}
if(cur.left != null){
deque.add(cur.left);
}
if(cur.right != null){
deque.add(cur.right);
}
}
}
return result;
}
};
|
112. 路径总和
题目链接：路径总和
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
65
66
67
68
69
|
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if(root == null){
return false;
}
Stack<TreeNode> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
stack1.push(root);
stack2.push(root.val);
while(!stack1.isEmpty()) {
int size =stack1.size();
for(int i = 0; i < size; i++) {
TreeNode cur = stack1.pop();
int value = stack2.pop();
if(cur.left == null && cur.right == null && value == sum) {
return true;
}
if(cur.left != null) {
stack1.push(cur.left);
stack2.push(value + cur.left.val);
}
if(cur.right != null) {
stack1.push(cur.right);
stack2.push(value + cur.right.val);
}
}
}
return false;
}
}
|
113. 路径总和 II
题目链接：路径总和 II
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
|
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
List<Integer> path = new LinkedList<>();
travesal(root, targetSum, res, path);
return res;
}
public void travesal(TreeNode root, int targetSum, List<List<Integer>> res, List<Integer> path) {
path.add(root.val);
if (root.left == null && root.right == null) {
if (targetSum - root.val == 0) {
res.add(new ArrayList<>(path));
}
return;
}
if (root.left != null) {
travesal(root.left, targetSum - root.val, res, path);
path.remove(path.size() - 1);
}
if (root.right != null) {
travesal(root.right, targetSum - root.val, res, path);
path.remove(path.size() - 1);
}
}
}
|
106. 从中序与后序遍历序列构造二叉树
题目链接：从中序与后序遍历序列构造二叉树
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 {
Map<Integer,Integer> map;
public TreeNode buildTree(int[] inorder, int[] postorder) {
map = new HashMap<>();
for(int i = 0;i < inorder.length;i++){
map.put(inorder[i],i);
}
return findNode(inorder,0,inorder.length,postorder,0,postorder.length);
}
public TreeNode findNode(int[] inorder,int inBegin,int inEnd,int[] postorder,int postBegin,int postEnd){
if (inBegin >= inEnd || postBegin >= postEnd) {
return null;
}
int rootValue = postorder[postEnd - 1];
int rootIndex = map.get(rootValue);
TreeNode root = new TreeNode(inorder[rootIndex]);
root.left = findNode(inorder,inBegin,rootIndex,
postorder,postBegin,postBegin + rootIndex - inBegin);
root.right = findNode(inorder,rootIndex + 1,inEnd,
postorder,postBegin + rootIndex - inBegin,postEnd - 1);
return root;
}
}
|
105. 从前序与中序遍历序列构造二叉树
题目链接：从前序与中序遍历序列构造二叉树
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 {
Map<Integer,Integer> map;
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);
}
public TreeNode findNode(int[] preorder,int preBegin,int preEnd,int[] inorder,int inBegin,int inEnd){
if(preBegin >= preEnd || inBegin >= inEnd){
return null;
}
int rootValue = preorder[preBegin];
int rootIndex = map.get(rootValue);
TreeNode root = new TreeNode(inorder[rootIndex]);
root.left = findNode(preorder,preBegin + 1,preBegin + rootIndex - inBegin + 1,
inorder,inBegin,rootIndex);
root.right = findNode(preorder,preBegin + rootIndex - inBegin + 1,preEnd,
inorder,rootIndex + 1,inEnd);
return root;
}
}
|
