[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