Binary Tree Traversal(二叉树遍历)

144. Binary Tree Preorder Traversal

题目描述

Given a binary tree, return the preorder traversal of its nodes’ values.

1
2
3
4
5
6
7
8
9
10
For example:
Given binary tree [1,null,2,3],
1
\
2
/
3
return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?

题目大意

二叉树前序遍历

解题思路

迭代,辅助栈
由于栈的特性,需先将右子树压栈

代码

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* public var val: Int
* public var left: TreeNode?
* public var right: TreeNode?
* public init(_ val: Int) {
* self.val = val
* self.left = nil
* self.right = nil
* }
* }
*/
class Solution {
func preorderTraversal(_ root: TreeNode?) -> [Int] {
guard let root = root else { return [] }
var stack = [root]
var ans = [Int]()
while !stack.isEmpty {
let tree = stack.removeLast()
ans.append(tree.val)
if let right = tree.right {
stack.append(right)
}
if let left = tree.left {
stack.append(left)
}
}
return ans
}
}

94. Binary Tree Inorder Traversal

题目描述

Given a binary tree, return the inorder traversal of its nodes’ values.

1
2
3
4
5
6
7
8
9
10
For example:
Given binary tree [1,null,2,3],
1
\
2
/
3
return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?

题目大意

二叉树中序遍历

解题思路

迭代,辅助栈
优先搜索左节点,当左节点为空时,再遍历根节点和右节点,循环以上步骤,采用辅助栈,保存根节点。

代码

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* public var val: Int
* public var left: TreeNode?
* public var right: TreeNode?
* public init(_ val: Int) {
* self.val = val
* self.left = nil
* self.right = nil
* }
* }
*/
class Solution {
func inorderTraversal(_ root: TreeNode?) -> [Int] {
var stack = [TreeNode?]()
var ans = [Int]()
var tree = root
while tree != nil || !stack.isEmpty {
while tree != nil {
stack.append(tree)
tree = tree?.left
}
tree = stack.removeLast()
ans.append(tree!.val)
tree = tree?.right
}
return ans
}
}

145. Binary Tree Postorder Traversal

题目描述

Given a binary tree, return the postorder traversal of its nodes’ values.

1
2
3
4
5
6
7
8
9
10
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?

题目大意

二叉树后序遍历

解题思路

迭代,辅助栈
遍历左右节点,当左右节点都为nil,或者左右节点都已被访问,可以输出当前节点的值,并出栈。根据栈先入后出的特性,需先将右节点压入栈。

代码

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* public var val: Int
* public var left: TreeNode?
* public var right: TreeNode?
* public init(_ val: Int) {
* self.val = val
* self.left = nil
* self.right = nil
* }
* }
*/
class Solution {
func postorderTraversal(_ root: TreeNode?) -> [Int] {
guard let root = root else { return [] }
var stack = [root]
var pre = root
var ans = [Int]()
while !stack.isEmpty {
if let tree = stack.last {
if (tree.left == nil && tree.right == nil)
|| (tree.left != nil && tree.left! === pre)
|| (tree.right != nil && tree.right! === pre) {
ans.append(tree.val)
stack.removeLast()
pre = tree
}else {
if let right = tree.right {
stack.append(right)
}
if let left = tree.left {
stack.append(left)
}
}
}
}
return ans
}
}

102. Binary Tree Level Order Traversal

题目描述

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

1
2
3
4
5
6
7
8
9
10
11
12
13
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]

题目大意

二叉树层序遍历

解题思路

第一种采用递归, BFS(广度优先搜索)

代码

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* public var val: Int
* public var left: TreeNode?
* public var right: TreeNode?
* public init(_ val: Int) {
* self.val = val
* self.left = nil
* self.right = nil
* }
* }
*/
class Solution {
func levelOrder(_ root: TreeNode?) -> [[Int]] {
var res = [[Int]]()
levelOperation(res: &res, root: root, level: 0)
return res
}
func levelOperation(res: inout [[Int]], root: TreeNode?, level: Int) {
guard let tree = root else{
return
}
if level >= res.count {
res.append([])
}
res[level].append(tree.val)
levelOperation(res: &res, root: tree.left, level: level + 1)
levelOperation(res: &res, root: tree.right, level: level + 1)
}
}

解题思路

第二种迭代,BFS(广度优先搜索)
利用Swift特性元祖,建立队列,将节点当前层数保留在队列。
给定ans变量作为结果,如果节点层数大于ans的数量,则先添加一个空数组到ans内,防止数组越界的情况。

代码

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* public var val: Int
* public var left: TreeNode?
* public var right: TreeNode?
* public init(_ val: Int) {
* self.val = val
* self.left = nil
* self.right = nil
* }
* }
*/
class Solution {
func levelOrder(_ root: TreeNode?) -> [[Int]] {
guard let root = root else { return [] }
var ans = [[Int]]()
var queue = [(0, root)]
while !queue.isEmpty {
let tree = queue.removeFirst()
if tree.0 >= ans.count {
ans.append([Int]())
}
ans[tree.0].append(tree.1.val)
if let left = tree.1.left {
queue.append((tree.0 + 1, left))
}
if let right = tree.1.right {
queue.append((tree.0 + 1, right))
}
}
return ans
}
}

107. Binary Tree Level Order Traversal II

题目描述

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

1
2
3
4
5
6
7
8
9
10
11
12
13
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]

题目大意

层序遍历,从底至上返回。

解题思路

和层序遍历思路差不多。
不同在于添加进数组时,需要插入到数组头。

代码

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* public var val: Int
* public var left: TreeNode?
* public var right: TreeNode?
* public init(_ val: Int) {
* self.val = val
* self.left = nil
* self.right = nil
* }
* }
*/
class Solution {
func levelOrderBottom(_ root: TreeNode?) -> [[Int]] {
guard let root = root else { return [] }
var ans = [[Int]]()
var queue = [(0, root)]
while !queue.isEmpty {
let tree = queue.removeFirst()
if tree.0 >= ans.count {
ans.insert([Int](), at: 0)
}
ans[ans.count - tree.0 - 1].append(tree.1.val) //与层序遍历的区别
if let left = tree.1.left {
queue.append((tree.0 + 1, left))
}
if let right = tree.1.right {
queue.append((tree.0 + 1, right))
}
}
return ans
}
}

103. Binary Tree Zigzag Level Order Traversal

题目描述

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

1
2
3
4
5
6
7
8
9
10
11
12
13
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]

题目大意

z型层序遍历二叉树,并以二维数组作为结果返回

解题思路

与层序遍历思路差不多。
不同点在于,需根据节点层数决定,ans添加节点值的方式(是insert还是append)。

代码

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* public var val: Int
* public var left: TreeNode?
* public var right: TreeNode?
* public init(_ val: Int) {
* self.val = val
* self.left = nil
* self.right = nil
* }
* }
*/
class Solution {
func zigzagLevelOrder(_ root: TreeNode?) -> [[Int]] {
guard let tree = root else {
return []
}
var ans = [[Int]]()
var queue = [(0, tree)]
while !queue.isEmpty {
let t = queue.removeFirst()
if t.0 >= ans.count {
ans.append([Int]())
}
if t.0 % 2 == 0 {
ans[t.0].append(t.1.val)
}else {
ans[t.0].insert(t.1.val, at: 0)
}
if let left = t.1.left {
queue.append((t.0 + 1, left))
}
if let right = t.1.right {
queue.append((t.0 + 1, right))
}
}
return ans
}
}
0%