发表于 | 分类于 |

98. Validate Binary Search Tree

题目描述

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.

1
2
3
4
5
6
7
8
9
10
Example 1:
    2
   / \
  1   3
Binary tree [2,1,3], return true.
Example 2:
    1
   / \
  2   3
Binary tree [1,2,3], return false.

题目大意

校验是否是二叉搜索树。

校验规则：

左子树的所有节点值都比根节点小；

右子树的所有节点值都比根节点大；

左子树和右子树也是二叉搜索树

解题思路

DFS，根据题目所述的规则进行判定即可。

代码

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
/**
 * 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 isValidBST(_ root: TreeNode?) -> Bool {
        
        guard let tree = root else { return true }
        
        var ans = true
        var rootVal = tree.val
        
        func dfs(_ t: TreeNode, min: Int, max: Int) {
            
            if let left = t.left {
                //是否小于根节点，通过max判定左子树是否都小于根节点
                if left.val >= t.val || left.val <= min || left.val >= max {
                    ans = false
                    return
                }
                dfs(left, min: min, max: t.val)
            }
            
            if let right = t.right {
                //是否大于根节点，通过min判定右子树是否都大于根节点
                if right.val <= t.val || right.val <= min || right.val >= max {
                    ans = false
                    return
                }
                dfs(right, min: t.val, max: max)
            }
        }
        
        dfs(tree, min: Int.min, max: Int.max)
        return ans
    }
}

发表于 | 分类于 |

738. Monotone Increasing Digits

题目描述

Given a non-negative integer N, find the largest number that is less than or equal to N with monotone increasing digits.

(Recall that an integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.)

1
2
3
4
5
6
7
8
9
Example 1:
Input: N = 10
Output: 9
Example 2:
Input: N = 1234
Output: 1234
Example 3:
Input: N = 332
Output: 299

Note: N is an integer in the range [0, 10^9].

题目大意

给定一整数N，找到小于等于N的最大单调递增数字。

解题思路

由高位到低位遍历整数N，找到第一个递减的数字。
记录最后一个连续相等的数字和下标记为v，直至第一个递减数字。例如12334551，我们只需要记录第一个5及其下标即可。
将v以后的所有数替换为0，再减一，加上递减之前的数字即可。

代码

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
func monotoneIncreasingDigits(_ N: Int) -> Int {
       let s = "\(N)"
       var ans = 0
       var v = (-1, -1)
       var flag = false
       for (i, char) in s.enumerated() {
           guard i + 1 < s.count else {
               break
           }
           let n = Int(String(char))!
           let next = Int(String(s[s.index(s.startIndex, offsetBy: i + 1)]))!
           if n > next {
               flag = true
               if v.0 == -1 || v.1 < n{
                   v = (i, n)
               }
               break
           }else if n == next && v.1 != n{
               v = (i, n)
           }
           ans = ans * 10 + n
       }
       guard flag else {
           return N
       }
       var digit = 1
       let power = s.count - v.0 - 1
       //由于leetcode使用pow函数报错，借以此代替幂操作
       for _ in 0..<power { digit *= 10 }
       return v.1 * digit - 1 + N / digit / 10 * digit * 10
   }

发表于 | 分类于 |

739. Daily Temperatures

题目描述

Given a list of daily temperatures, produce a list that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list temperatures = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000].
Each temperature will be an integer in the range [30, 100].

题目大意

给定一组每日的气温，每一天最少需要等到多少天温度才能升高，如果没有，则输出0.

例如，每日温度=[73,74,75,71,69,72,76,73]，你的输出应该是[1,1,4,2,1,1,0,0]。

注:温度的长度范围为[1,30000]。
每个温度将是范围内的整数[30,100]。

解题思路

采用Stack + tuple的方式
建立元祖代表下标和温度，使用Array代替Stack
遍历温度列表，将下标和温度压栈。
循环判断栈顶温度是否大于当前温度，如果大于则出栈，否则停止循环。
通过上述操作维护了一个递增栈。

代码

1
2
3
4
5
6
7
8
9
10
11
12
func dailyTemperatures(_ temperatures: [Int]) -> [Int] {
    var stack = [(index: Int, value: Int)]()
    var ans = Array(repeating: 0, count: temperatures.count)
    for (i, t) in temperatures.enumerated() {
        while !stack.isEmpty && stack.last!.value < t {
            let top = stack.removeLast()
            ans[top.index] = i - top.index
        }
        stack.append((index: i,value: t))
    }
    return ans
}

发表于 | 分类于 |

606. Construct String from Binary Tree

题目描述

You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way.

The null node needs to be represented by empty parenthesis pair “()”. And you need to omit all the empty parenthesis pairs that don’t affect the one-to-one mapping relationship between the string and the original binary tree.

1
2
3
4
5
6
7
8
9
10
11
12
Example 1:
Input: Binary tree: [1,2,3,4]
       1
     /   \
    2     3
   /    
  4     
Output: "1(2(4))(3)"
Explanation: Originallay it needs to be "1(2(4)())(3()())", 
but you need to omit all the unnecessary empty parenthesis pairs. 
And it will be "1(2(4))(3)".
1
2
3
4
5
6
7
8
9
10
11
12
Example 2:
Input: Binary tree: [1,2,3,null,4]
       1
     /   \
    2     3
     \  
      4 
Output: "1(2()(4))(3)"
Explanation: Almost the same as the first example, 
except we can't omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.

题目大意

将二叉树转换为字符串，转换规则为root(left)(right)，以此类推

解题思路

递归
ps:不知道该咋说，代码一目了然。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 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 tree2str(_ t: TreeNode?) -> String {
        guard let tree = t else { return "" }
        if tree.left == nil && tree.right == nil { return "\(tree.val)" }
        else if tree.left == nil { return "\(tree.val)" + "()" + "(\(tree2str(tree.right)))" }
        else if tree.right == nil { return "\(tree.val)" + "(\(tree2str(tree.left)))" }
        else { return "\(tree.val)" + "(\(tree2str(tree.left)))" + "(\(tree2str(tree.right)))" }
    }
}

发表于 | 分类于 |

450. Delete Node in a BST

题目描述

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

Search for a node to remove.
If the node is found, delete the node.
Note: Time complexity should be O(height of tree).

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
Example:
root = [5,3,6,2,4,null,7]
key = 3
    5
   / \
  3   6
 / \   \
2   4   7
Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the following BST.
    5
   / \
  4   6
 /     \
2       7
Another valid answer is [5,2,6,null,4,null,7].
    5
   / \
  2   6
   \   \
    4   7

题目大意

删除二叉树节点

解题思路

遍历二叉树，找到目标节点。
如果目标节点左子树或右子树为nil,则将目标节点与其替换。
如果目标节点左右子树都不为nil,则将左子树与目标节点替换，为使二叉树在删除节点后，仍然保留二叉树特性。需以左子树为key,重复以上操作。

代码

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
/**
 * 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 deleteNode(_ root: TreeNode?, _ key: Int) -> TreeNode? {
        guard let tree = root else { return root }
        if tree.val > key {
            tree.left = deleteNode(tree.left, key)
        }
        else if tree.val < key {
            tree.right = deleteNode(tree.right, key)
        }
        else {
            if tree.left == nil {
                return tree.right
            }else if tree.right == nil {
                return tree.left
            }
            var node = tree.left
            while node?.right != nil {
                node = node?.right
            }
            tree.val = node!.val
            tree.left = deleteNode(tree.left, tree.val)
        }
        return tree
    }
}

发表于 | 分类于 |

198. House Robber

题目描述

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

题目大意

小偷打算在街上抢劫房屋，每户都会存放一定数额的现金，以nums表示，唯一的限制是，如果每相邻的两家同一晚上被盗就会自动联系警察。求今晚能偷到的最大金额

解题思路

动态规划
根据下标将数组分为奇数和偶数，以此确保两个相邻的不会被偷，设奇数和偶数变量分别为even、odd。
even表示打劫到奇数下标时所能累计的最大值，odd亦然。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    func rob(_ nums: [Int]) -> Int {
        var even = 0
        var odd = 0
        for i in 0..<nums.count {
            if i % 2 == 0 {
                even = max(even + nums[i], odd)
            }else {
                odd = max(odd + nums[i], even)
            }
        }
        return max(even, odd)
    }
}

213. House Robber II

题目描述

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

题目大意

House Robber的扩展，小偷找到新的目标，但是这条街上所有的房屋是环形，即第一个房屋和最后一个房屋是相邻，警报的规则同House Robber相同。

解题思路

具体实现思路与House Robber
不同的是需要把第一个数从数组中移除，数组记为nums1；最后一个从数组中移除，数组记为nums2。如此才能保证第一个房屋和最后一个房屋不同时被偷。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    func rob(_ nums: [Int]) -> Int {
        func auxiliary(nums: [Int]) -> Int {
            var even = 0
            var odd = 0
            for i in 0..<nums.count {
                if i % 2 == 0 {
                    even = max(even + nums[i], odd)
                }else {
                    odd = max(odd + nums[i], even)
                }
            }
            return max(even, odd)
        }
        if nums.count == 1 { return nums[0] }
        if nums.count == 0 { return 0 }
        var nums1 = nums
        var nums2 = nums
        nums1.removeFirst()
        nums2.removeLast()
        return max(auxiliary(nums: nums1), auxiliary(nums: nums2))
    }
}

发表于 | 分类于 |

96. Unique Binary Search Trees

题目描述

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

1
2
3
4
5
6
7
8
For example,
Given n = 3, there are a total of 5 unique BST's.
   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

题目大意

给定一数字n，求有多少个BST组合。

解题思路

动态规划
如果n=1，ans=1。
如果n=2，ans=2。
如果n=3，ans=5。
如果n=4，ans=14。
可以发现规律：
f(0)=1
f(1)=f(0)
f(2)=f(0)f(1) + f(1)f(0)
f(3)=f(0)f(2) + f(1)f(1) + f(2)f(0)
f(4)=f(0)f(3) + f(1)f(2) + f(2)f(1) + f(3)f(0)
.
.
.
f(n)=f(0)f(n-1) + f(1)f(n-2) + …+f(n-1)f(0)

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    func numTrees(_ n: Int) -> Int {
        var dp = Array(repeating: 0, count: n + 1)
        dp[0] = 1
        for i in 1...n {
            for j in 0..<i {
                dp[i] += dp[j] * dp[i - 1 - j]
            }
        }
        return dp[n]
    }
}

95. Unique Binary Search Trees II

题目描述

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1…n.

1
2
3
4
5
6
7
8
For example,
Given n = 3, your program should return all 5 unique BST's shown below.
   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

题目大意

给定一数字n，返回BST组合。跟I不同的是这里需要返回具体的BST。

解题思路

动态规划
使用递归生成左右节点，再将所有左右节点加在根节点。

代码

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
class Solution {
    func generateTrees(_ n: Int) -> [TreeNode?] {
        
        func recursion(min: Int, max: Int) -> [TreeNode?] {
            var ans = [TreeNode?]()
            guard min <= max else{ return [nil] }
            for i in min...max {
                let left = recursion(min: min, max: i - 1)
                let right = recursion(min: i + 1, max: max)
                for l in left {
                    for r in right {
                        let t = TreeNode(i)
                        t.left = l
                        t.right = r
                        ans.append(t)
                    }
                }
            }
            return ans
        }
        
        guard n != 0 else{ return [] }
        return recursion(min: 1, max: n)
    }
}

发表于 | 分类于 |

129. Sum Root to Leaf Numbers

题目描述

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

1
2
3
4
5
6
7
8
9
For example,
    1
   / \
  2   3
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.

题目大意

根节点到子节点的路径代表一个数，求所有路径的数值的和。

1
2
3
4
5
6
7
    1
   / \
  2   3
根节点到子节点的路径 1->2 代表数值：12
根节点到子节点的路径 1->3 代表数值：13
返回结果 25

解题思路

DFS(深度优先搜索)
遍历左右子树，直到左右子树都为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
/**
 * 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 sumNumbers(_ root: TreeNode?) -> Int {
        var ans = 0
        func dfs(tree: TreeNode?, pre: Int) -> Int {
            guard let t = tree else { return 0 }
            let n = pre * 10 + t.val
            if t.left == nil && t.right == nil {
                return n
            }
            return dfs(tree: t.left, pre: n) + dfs(tree: t.right, pre: n)
        }
        return dfs(tree: root, pre: 0)
    }
}

发表于 | 分类于 |

105. Construct Binary Tree from Preorder and Inorder Traversal

题目描述

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

题目大意

根据前序和中序，构建二叉树。

解题思路

由于前序遍历的规则是：根->左->右，所以前序遍历的第一个元素为根节点，根据这一特性，将中序数组分为左子树和右子树。重复以上操作。

代码

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
/**
 * 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 buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
       var dict = [Int: Int]() //参考leetcode上的最优解决方案，优化
        for (i, n) in inorder.enumerated() {
            dict[n] = i
        }
        func build(preIndex: Int, start: Int, end: Int) -> TreeNode? {
            guard start <= end else { return nil }
            
            let root = TreeNode(preorder[preIndex])
            let index = dict[preorder[preIndex]] ?? 0
            
            if index > start {
                root.left = build(preIndex: preIndex + 1, start: start, end: index - 1)
            }
            if index < end {
                //由于preIndex + 1之后，首元素其实是左子树，所以需要加上当前inorder数组中，左子树的个数，才能将首元素变为右子树。
                root.right = build(preIndex: preIndex + index - start + 1, start: index + 1, end: end)
            }
            
            return root
        }
        
        return build(preIndex: 0, start: 0, end: inorder.count - 1)
    }
}

106. Construct Binary Tree from Inorder and Postorder Traversal

题目描述

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

题目大意

根据后序和中序，构建二叉树

解题思路

与前序和中序构建树的思路差不多。
需要使用后序特性，最后一个数为根节点。将前序数组分为左右两个子树。

代码

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
/**
 * 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 buildTree(_ inorder: [Int], _ postorder: [Int]) -> TreeNode? {
        var dict = [Int: Int]() //参考leetcode上的最优解决方案，优化
        for (i, n) in inorder.enumerated() {
            dict[n] = i
        }
        func build(postStart: Int, postEnd: Int, inStart: Int, inEnd: Int) -> TreeNode? {
            guard inStart <= inEnd && postStart <= postEnd else { return nil }
            
            let root = TreeNode(postorder[postEnd])
            let index = dict[postorder[postEnd]] ?? 0
            
            if index > inStart {
                root.left = build(postStart: postStart, postEnd: postStart + index - inStart - 1, inStart: inStart, inEnd: index - 1)
            }
            if index < inEnd {
                root.right = build(postStart: postStart + index - inStart, postEnd: postEnd - 1, inStart: index + 1, inEnd: inEnd)
            }
            
            return root
        }
        
        return build(postStart: 0, postEnd: postorder.count - 1, inStart: 0, inEnd: inorder.count - 1)
    }
}

发表于 | 分类于 |

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%