LeetCode #94 Binary Tree Inorder Traversal

Posted on | Post modified | In , , , , , , , ,

Problem

Given a binary tree, return the inorder traversal of its nodes’ values.

Example

1
2
3
4
5
6
7
8
Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]

Solution

Method: Recursive

Time Complexity: O(n)

Space Complexity: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        def helper(root, res):
            if root:
                helper(root.left, res)
                res.append(root.val)
                helper(root.right, res)

        res = []
        helper(root, res)
        
        return res

or

1
2
3
4
5
6
7
8
9
10
11
12
def recursive(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []

        left = self.inorderTraversal(root.left)
        right = self.inorderTraversal(root.right)

        return left + [root.val] + right

Solution2

Method: Depth First Search

Time Complexity: O(n)

Space Complexity: O(n)

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
class Solution:
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        
        stack = [[root, False]]
        ret = []
        
        while stack:
            elem, visited = stack[-1]

            if visited:
                ret.append(elem.val)
                stack.pop()
                if elem.right:
                    stack.append([elem.right, False])
            else:
                stack[-1][1] = True
                if elem.left:
                    stack.append([elem.left, False])
        
        return ret