二叉树一些个人总结

在github wiki功能开始帖子总结一些典型算法，这里是花了一个周末学习的二叉树，欢迎指教！！
https://github.com/Issac-F/Algorithm-Ocean/wiki/%E4%BA%8C%E5%8F%89%E6%A0%91

+1 这个算是浅显易懂

总结好评！
（提供一下前中后traversal的迭代、递归代码 https://shawnlyu.com/algorithms/40/
（以及几个分治法的练习：
（148. Sort List
（23. Merge k Sorted Lists
（215. Kth Largest Element in an Array

如果有PYTHON版的就更好啦！

请问面试的时候碰到任何tree的问题，如果只给出iterative solution的话一般会加问recursive solution吗？ 个人觉得iteration比较intuitive， recursion基本想不出来

# Binary search tree

## Table of Contents

1. [Traversal](#traversal)
   - [In-order](#in-order)
   - [Pre-order](#pre-order)
   - [Post-order](#post-order)
   - [Breath-first-search](#BFS)
  
## Traversal <a name="traversal"></a>

- In-order (Left Root Right) <a name="in-order"></a>
  
        # Definition for a binary tree node.
        # class TreeNode(object):
        #     def __init__(self, x):
        #         self.val = x
        #         self.left = None
        #         self.right = None

        # Use recursion
        def inorder_recursive (root):
            if root == None:
                return
            inorder_recursive(root.left)
            do_something_about(root)
            inorder_recursive(root.right)

        # Use stack
        def inorder_nonrecursive(root):
            stack = []
            node = root

            while True:
                if node != None:
                    stack.append(node)
                    node = node.left
                else:
                    if len(stack) == 0:
                        break
                    node = stack.pop()
                    do_something_about(node)
                    node = node.right

- Pre-order (Root, Left, Right) <a name="pre-order"></a>

        # Use recursion
        def preorder_recursive(root):
            if root == None:
                return
            do_something_about(root)
            preoder_recursive(root.left)
            preorder_recursive(root.right)

        # Use stack
        def preorder_nonrecursive(root):
            stack = []
            node = root

            while True:
                if node != None:
                    do_something_about(node)
                    if node.right != None:
                        stack.append(node.right)
                    node = node.left
                else:
                    if len(stack) == 0:
                        break
                    node = stack.pop()

- Post-order (Left, Right, Root) <a name="post-order"></a>

        # Use recursion
        def postorder_recursive(root):
            if root == None:
                return
            postorder_recursive(root.left)
            postorder_recursive(root.right)
            do_something_about(root)

        # Use stack
        def postorder_nonrecursive(root):
            stack = []
            node = root

            while True:
                if node != None:
                    stack.append((node, False))
                    node = node.left
                else:
                    if len(stack) == 0:
                        break
                    node, visited = stack.pop()
                    if not visited:
                        stack.append((node, True))
                        node = node.right
                    else:
                        do_something_about(node)
                        node = None         # force to come back to the 'else' branch in next iteration

- Breath-first-search <a name="BFS"></a>

        # Use queue
        def BFS_BST(root):
            if root == None:
                return
            queue = [root]
            while queue:
                node = queue.pop(0)
                do_something_about(node)
                if node.left != None:
                    queue.append(node.left)
                if node.right != None:
                    queue.append(node.right)