199. 二叉树的右视图

解法一 BFS 广度优先 层序遍历

• 时间复杂度
  O(n) 每个节点访问一次
• 空间复杂度
  O(n)

func rightSideView(_ root: TreeNode?) -> [Int] {
        guard let root = root else { return [] }
        var ans: [Int] = []
        var treeList = [root]

        while !treeList.isEmpty {
            let count = treeList.count
            for i in 0 ..< count {
                let tree = treeList.remove(at: 0)
                if i == count - 1 {
                    ans.append(tree.val)
                }
                if tree.left != nil {
                    treeList.append(tree.left!)
                }
                if tree.right != nil {
                    treeList.append(tree.right!)
                }
            }
        }

        return ans
    }

解法二 DFS 深度优先 前序遍历 变形

• 时间复杂度
  O(n) 每个节点访问一次
• 空间复杂度
  O(n)

var ans: [Int] = []
    func rightSideView(_ root: TreeNode?) -> [Int] {
        dfsSlideView(root, 0)
        return ans
    }

    func dfsSlideView(_ root: TreeNode?, _ depth: Int) {
        guard let root = root else { return }
        if depth == ans.count {
            ans.append(root.val)
        }
        let d = depth + 1
        dfsSlideView(root.right, d)
        dfsSlideView(root.left, d)
    }