2020-04-22

针对199 树的左视图，右视图。

层序遍历，广度优先，是首先想到的。
第二，就是用DFS。而这里的优化思想，
1）来自对字典的get 的认识。
2）基于栈的递归。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        if not root:return []
        s=[(root,0)];d={}
        while s:
            node,depth=s.pop()
            d[depth]=d.get(depth,node.val)   #没穿防火服，给你一个，有了干活去。
            #drill down 
            if node.left:s.append((node.left,depth+1))
            if node.right:s.append((node.right,depth+1))
        return [d[i] for i in range(len(d))]

层序遍历

class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        if not root:return []
        from collections import deque
        q,a=deque(),[];q.append(root)
        while q:
            level,t=len(q),[]
            for i in range(level):
                c=q.popleft()
                t.append(c.val)
                if c.left : q.append(c.left)
                if c.right: q.append(c.right)
            a.append(t[-1])
        return a

deque 的使用，以及c=q.popleft()