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%