Tate Blog

iOS Developer

0%

Swift Leetcode 二叉树 算法题解

Posted on In

1.二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：

img

1
2
输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2：

1
2
输入：root = []
输出：[]
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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func preorderTraversal(_ root: TreeNode?) -> [Int] {
        var result = [Int]()
        guard let root = root else {
            return result
        }
        result.append(root.val)
        result += preorderTraversal(root.left)
        result += preorderTraversal(root.right)
        return result
    }
}

解题思路：

  1. 前序遍历按照根节点->左子树->右子树的顺序访问
  2. 访问根节点
  3. 采用中序递归遍历左子树
  4. 采用中序递归遍历右子树

2.二叉树的中序遍历

给定一个二叉树的根节点 root ，返回它的 中序 遍历。

示例 1：

img

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

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

解题思路：

  1. 中序遍历按照左子树->根节点->右子树的顺序访问
  2. 采用中序递归遍历左子树
  3. 访问根节点
  4. 采用中序递归遍历右子树

3.二叉树的后序遍历

给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3]
1

2
/
3

输出: [3,2,1]

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

解题思路：

  1. 后序遍历按照左子树->右子树的顺序访问->根节点
  2. 采用后序递归遍历左子树
  3. 采用后序递归遍历右子树
  4. 访问根节点

4.二叉树的层序遍历

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：
二叉树：[3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

返回其层序遍历结果：

1
2
3
4
5
[
  [3],
  [9,20],
  [15,7]
]
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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
/** 层序遍历 */
func levelOrderTranversal(_ root: TreeNode?) -> [Int] {
    guard let root = root else {return []}
    var result = [Int]()
    var queue = [TreeNode?]()
    queue.append(root)
    while !queue.isEmpty {
        //出队
        let node =  queue.removeFirst()
        result.append(node?.val ?? 0)
        if node?.left != nil {
            queue.append(node?.left)
        }
 
        if node?.right != nil {
            queue.append(node?.right)
        }
    }
    
    return result
}

解题思路：

  1. 将根节点入队
  2. 循环执行以下操作，直到队列为空
    1. 将根节点node出队，进行访问
    2. 将node的左子节点入队
    3. 将node的右子节点入队

不过题目要求每个层级都分出来改成二维数组，那需要改动下

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
class Solution {
    func levelOrder(_ root: TreeNode?) -> [[Int]] {
        guard let root = root else {return []}
        var result = [[Int]]()
        //队列先进先出的特性
        var queue = [TreeNode?]()
        queue.append(root)
        while !queue.isEmpty {
            var level = [Int]()
            //同时在队列里的元素都属于同一层的，都遍历出来
            for _ in 0..<queue.count {
                //出队
                let node =  queue.removeFirst()
                level.append(node?.val ?? 0)
                if node?.left != nil {
                    queue.append(node?.left)
                }
                
                if node?.right != nil {
                    queue.append(node?.right)
                }
            }
            result.append(level)
        }
        return result
    }
}

解题思路：

这里可以确定同时在队列里的元素都是同一个层级的，所以我们直接在每次while循环遍历出所有元素即可。