binary-tree-right-side-view.md

title	description	authors	tags	categories	date	draft	archive
Binary Tree Right Side View	Some description ...	lek-tin	leetcode binary-tree	algorithm	2018-09-13 23:03:06 +0800	false	false

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.

Example

Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

Solution

# 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):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []

        def pick(root, level):
            if root != None:
                if level == len(res):
                    res.append(root.val)
                pick(root.right, level + 1)
                pick(root.left, level + 1)

        pick(root, 0)
        return res

# 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):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        self.iterate(res, root, 0)
        return res

    def iterate(self, res, node, level):
        if node == None:
            return

        if len(res) == level:
            res.append(node.val)
        else:
            res[level] = node.val

        if node.left:
            self.iterate(res, node.left, level+1)
        if node.right:
            self.iterate(res, node.right, level+1)

# 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]:
        res = []
        self.helper(root, res, 0)
        return res

    def helper(self, root, res, level):
        if not root:
            return

        if len(res) <= level:
            res.append(root.val)

        self.helper(root.right, res, level+1)
        self.helper(root.left, res, level+1)