[LeetCode] questions conlusion_InOrder, PreOrder, PostOrder traversal

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Pre: node 先, Inorder: node in, Postorder: node 最后

PreOrder	Inorder	PostOrder
node -> left -> right	left -> node ->right	left -> right -> node

Recursive method

实际上代码是一样, 就是把ans.append(root.val) 放在如上表先, 中, 后就是pre, in, post order了.

1) PreOrder traversal

ans = []

def preOrder(self, root):

    if not root: return

    ans.append(root.val)

    preOrder(root.left)

    preOrder(root.right)

preOrder(root)

return ans

2) Inorder traversal Worst S: O(n), average is O(lgn)

ans = []

def inOrder(self, root):

    if not root: return

    inOrder(root.left)

    ans.append(root.val)

    inOrder(root.right)

inOrder(root)

return ans

3) PostOrder traversal

ans = []

def postOrder(self, root):

    if not root: return

    postOrder(root.left)

    postOrder(root.right)

    ans.append(root.val)



postOrder(root)

return ans

Iterable method

1) Preorder traversal --- Just use stack .

node -> left -> right

def Preorder(self, root):

    if not root: return []

    ans, stack = [], [root]

    while stack:

        node = stack.pop()

        ans.append(node.val)

        if node.right:

            stack.append(node.right)

        if node.left:

            stack.append(node.left)

    return ans

2) inOrder traversal

left -> node ->right

def inOrder(self, root):

    ans, stack = [], []

    while True:

        while root:

            stack.append(root)

            root = root.left

        if not stack: return ans

        node = stack.pop()

        ans.append(node.val)

        root = node.right

seconde inOrder traversal

def inOrder(self, root):

    ans, stack = [], []

    while stack or root:

        if root:

            stack.append(root)

            root = root.left

        else:

            node = stack.pop()

            ans.append(node.val)

            root = node.right

     return ans

3) PostOrder traversal

left -> right -> node

由于我们已经知道如何用preorder, 所以我们知道用 node -> left -> right, 所以我们可以用类似于preorder的做法, 将 node -> right -> left 做出来, 最后返回reverse 的ans即可.

def PostOrder(self, root):

    if not root: return []

    stack, ans = [root], []

    while stack:

        node = stack.pop()

        ans.append(node.val)

        if node.left:

            stack.append(node.left)

        if node.right:

            stack.append(node.right)

     return ans[::-1]

second PostOrder traversal

利用hash table, 但是我们直接将这个hash table append进入stack, 跟node形成一个tuple.

def PostOrder(self, root):

    if not root: return []

    stack, ans = [(root, False)], []

    while stack:

        node, visited  = stack.pop()

        if visited:

            ans.append(node.val)

        else:

            stack.append((node, True))

            if node.right:

                stack.append((node.right, False))

            if node.left:

                stack.append((node.left, False))

    return ans

Questions:

[LeetCode]94, 144, 145 Binary Tree InOrder, PreOrder, PostOrder Traversal_Medium

[LeetCode] 589. N-ary Tree Preorder Traversal_Easy

[LeetCode] 590. N-ary Tree Postorder Traversal_Easy

[LeetCode] 98. Validate Binary Search Tree_Medium

[LeetCode] 230. Kth Smallest Element in a BST_Medium tag: Inorder Traversal

[LeetCode] 285. Inorder Successor in BST_Medium tag: Inorder Traversal

[LeetCode] 105. Construct Binary Tree from Preorder and Inorder Traversal_Medium tag: Tree Traversal

[LeetCode] 106. Construct Binary Tree from Postorder and Inorder Traversal_Medium tag: Tree Traversal

[LeetCode] 255. Verify Preorder Sequence in Binary Search Tree_Medium tag: Preorder Traversal, tree

[LeetCode] 331. Verify Preorder Serialization of a Binary Tree_Medium tag: stack