leetcode

Binary Tree Inorder Traversal

Binary Tree Inorder Traversal

中序遍历(In-Order Traversal)

指先访问左（右）子树，然后访问根，最后访问右（左）子树的遍历方式

Recursive 递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        ret = []
        if not root:
            return ret
        if root.left != None:
            ret += self.inorderTraversal(root.left)
        ret += [root.val]
        if root.right != None:
            ret += self.inorderTraversal(root.right)
        return ret

Iteratively 非递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        ret = []
        stack = []
        while True:
            while root:
                stack.append(root)
                root = root.left
            if not stack: return ret
            node = stack.pop()
            ret.append(node.val)
            root = node.right
        return ret

test code

1
2
3
4
5
6
7
8
9
10
11
12
13
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
tree = TreeNode(1)
tree.right = TreeNode(2)
tree.right.left = TreeNode(3)
s = Solution(); s.inorderTraversal(tree)

result

1
2
In [66]: s = Solution(); s.inorderTraversal(tree)
Out[66]: [1, 3, 2]

树的遍历#中序遍历(In-Order_Traversal))

leet code