199. Binary Tree Right Side View

发表于 | 分类于 | |

199. Binary Tree Right Side View

题目描述

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

1
2
3
4
5
6
7
8
For example:
Given the following binary tree,
   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---
You should return [1, 3, 4].

题目大意

给定一二叉树，求二叉树的右视图。
例如，从右边看二叉树，你应该返回结果为：[1, 3, 4]。

解题思路

层序遍历，辅助栈。
只将当前层的最右节点加入数组，通过flag参数标记当前层是否已经有节点被加入到数组内。

代码

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
/**
 * 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 rightSideView(_ root: TreeNode?) -> [Int] {
        guard let tree = root else { return [] }
        
        var ans = [Int]()
        var stack = [(0, tree)]
        var flag = 0
        
        while !stack.isEmpty {
            let t = stack.removeLast()
            if t.0 == flag {
                ans.append(t.1.val)
                flag = t.0 + 1
            }
            if let l = t.1.left {
                stack.append((t.0 + 1, l))
            }
            if let r = t.1.right {
                stack.append((t.0 + 1, r))
            }
        }
        return ans
    }
}
0%