Movatterモバイル変換


[0]ホーム

URL:


Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Sign up
Appearance settings

Commite93c329

Browse files
author
applewjg
committed
BinaryTreeLevelOrderTraversal I && II
1 parentd3aa77c commite93c329

File tree

2 files changed

+138
-0
lines changed

2 files changed

+138
-0
lines changed

‎BinaryTreeLevelOrderTraversal.java

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
/*
2+
Author: King, wangjingui@outlook.com
3+
Date: Dec 12, 2014
4+
Problem: Binary Tree Level Order Traversal
5+
Difficulty: easy
6+
Source: https://oj.leetcode.com/problems/binary-tree-level-order-traversal/
7+
Notes:
8+
Given a binary tree, return the level order traversal of its nodes' values.
9+
(ie, from left to right, level by level).
10+
11+
For example:
12+
Given binary tree {3,9,20,#,#,15,7},
13+
3
14+
/ \
15+
9 20
16+
/ \
17+
15 7
18+
return its level order traversal as:
19+
[
20+
[3],
21+
[9,20],
22+
[15,7]
23+
]
24+
25+
Solution: 1. Use queue. In order to seperate the levels, use 'NULL' as the end indicator of one level.
26+
2. DFS.
27+
*/
28+
29+
/**
30+
* Definition for binary tree
31+
* public class TreeNode {
32+
* int val;
33+
* TreeNode left;
34+
* TreeNode right;
35+
* TreeNode(int x) { val = x; }
36+
* }
37+
*/
38+
publicclassSolution {
39+
publicList<List<Integer>>levelOrder_1(TreeNoderoot) {
40+
List<List<Integer>>res =newArrayList<List<Integer>>();
41+
if (root ==null)returnres;
42+
Queue<TreeNode>q =newLinkedList<TreeNode>();
43+
q.offer(root);
44+
q.offer(null);
45+
List<Integer>level =newArrayList<Integer>();
46+
47+
while(true) {
48+
TreeNodenode =q.poll();
49+
if (node !=null) {
50+
level.add(node.val);
51+
if(node.left!=null)q.offer(node.left);
52+
if(node.right!=null)q.offer(node.right);
53+
}else {
54+
res.add(level);
55+
level =newArrayList<Integer>();
56+
if(q.isEmpty()==true)break;
57+
q.offer(null);
58+
}
59+
}
60+
returnres;
61+
}
62+
63+
publicList<List<Integer>>levelOrder_2(TreeNoderoot) {
64+
List<List<Integer>>res =newArrayList<List<Integer>>();
65+
if (root ==null)returnres;
66+
levelOrderRe(root,0,res);
67+
returnres;
68+
}
69+
publicvoidlevelOrderRe(TreeNoderoot,intlevel,List<List<Integer>>res) {
70+
if(root ==null)return;
71+
if(level ==res.size())res.add(newArrayList<Integer>());
72+
res.get(level).add(root.val);
73+
levelOrderRe(root.left,level+1,res);
74+
levelOrderRe(root.right,level+1,res);
75+
}
76+
}

‎BinaryTreeLevelOrderTraversalII.java

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
/*
2+
Author: King, wangjingui@outlook.com
3+
Date: Dec 12, 2014
4+
Problem: Binary Tree Level Order Traversal II
5+
Difficulty: easy
6+
Source: https://oj.leetcode.com/problems/binary-tree-level-order-traversal-ii/
7+
Notes:
8+
Given a binary tree, return the bottom-up level order traversal of its nodes' values.
9+
(ie, from left to right, level by level from leaf to root).
10+
11+
For example:
12+
Given binary tree {3,9,20,#,#,15,7},
13+
3
14+
/ \
15+
9 20
16+
/ \
17+
15 7
18+
return its bottom-up level order traversal as:
19+
[
20+
[15,7]
21+
[9,20],
22+
[3],
23+
]
24+
25+
Solution: Queue version. On the basis of 'Binary Tree Level Order Traversal', reverse the final vector.
26+
*/
27+
28+
/**
29+
* Definition for binary tree
30+
* public class TreeNode {
31+
* int val;
32+
* TreeNode left;
33+
* TreeNode right;
34+
* TreeNode(int x) { val = x; }
35+
* }
36+
*/
37+
publicclassSolution {
38+
publicList<List<Integer>>levelOrderBottom(TreeNoderoot) {
39+
List<List<Integer>>res =newArrayList<List<Integer>>();
40+
if (root ==null)returnres;
41+
Queue<TreeNode>q =newLinkedList<TreeNode>();
42+
q.offer(root);
43+
q.offer(null);
44+
List<Integer>level =newArrayList<Integer>();
45+
46+
while(true) {
47+
TreeNodenode =q.poll();
48+
if (node !=null) {
49+
level.add(node.val);
50+
if(node.left!=null)q.offer(node.left);
51+
if(node.right!=null)q.offer(node.right);
52+
}else {
53+
res.add(level);
54+
level =newArrayList<Integer>();
55+
if(q.isEmpty()==true)break;
56+
q.offer(null);
57+
}
58+
}
59+
Collections.reverse(res);
60+
returnres;
61+
}
62+
}

0 commit comments

Comments
 (0)

[8]ページ先頭

©2009-2025 Movatter.jp