144_Binary Tree Preorder Traversal

144. Binary Tree Preorder Traversal

Level: medium

Tag: tree, stack

Question

Given a binary tree, return the preorder traversal of its nodes' values.

Example 1

Given binary tree [1,null,2,3],

   1
    \
     2
    /
   3

return [1,2,3]

Solution 1: recursive

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

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        ret = []
        self.dfs(root, ret)
        return ret


    def dfs(self, root, ret):
        """
        :type root: TreeNode
        :rtype List[int]
        """
        if root:
            ret.append(root.val)
            self.dfs(root.left, ret)
            self.dfs(root.right, ret)

Another version (w/o defining a helper function)

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

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        # if root is empty, return empty list
        if not root:
            return []

        # ow, return root value, then left valus and right values
        ret = [root.val]
        if root.left:
            ret += self.preorderTraversal(root.left)
        if root.right:
            ret += self.preorderTraversal(root.right)
        return ret

Solution 2: itratively

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

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        stack = [root]
        ret = []

        while stack:
            node = stack.pop()
            if node:
                ret.append(node.val)
                stack.append(node.right)
                stack.append(node.left)
        return ret