二叉树相关

二叉树是一种常用的数据结构，其涉及的相关算法也较多，简单做一些总结
在二叉树中，每个节点最多只有两个子树，即左子树和右子树。
性质
1.在一个非空二叉树的第n层上至多有2^(n-1)个元素。

2.一个深度为h的二叉树至多有2^h-1个结点。

满二叉树：所有终端都在同一层次，且非终端结点的度数为2。

在满二叉树中若其深度为h，则其所包含的结点数必为2^h-1。

class BTree(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

二叉树的遍历
二叉树的遍历是将二叉树的所有节点都访问且只访问一次，根据根节点的访问顺序又分为前序遍历、中序遍历和后序遍历。
前序遍历：左子树 -> 根节点 -> 右子树
中序遍历：根节点 ->左子树 -> 右子树
后序遍历：左子树 -> 右子树 -> 根节点
其递归实现：

@staticmethod
    def preorder_rec(tree_root):
        '''
        root -> left -> right
        递归版本，效率低
        '''
        if not tree_root:
            return
        else:
            print(tree_root.value)
            BTree.preorder_rec(tree_root.left)
            BTree.preorder_rec(tree_root.right)
    
    @staticmethod
    def midorder_rec(tree_root):
        '''
        left -> root -> right
        '''
        if not tree_root:
            return
        else:
            BTree.midorder_rec(tree_root.left)
            print(tree_root.value)
            BTree.midorder_rec(tree_root.right)
    
    @staticmethod
    def postorder_rec(tree_root):
        '''
        left -> right -> root
        '''
        if not tree_root:
            return
        else:
            BTree.postorder_rec(tree_root.left)
            BTree.postorder_rec(tree_root.right)
            print(tree_root.value)

递归实现通常效率低，加下来实现非递归版本。

@staticmethod
    def preorder(tree_root):
        '''
        root -> left -> right
        '''
        stack = [] # 用列表模拟栈
        while tree_root or stack:
            if tree_root:
                print(tree_root.value)
                stack.append(tree_root)
                tree_root = tree_root.left
            else:
                node = stack.pop()
                tree_root = node.right
                
    @staticmethod            
    def midorder(tree_root):
        '''
        left -> root -> right
        '''
        stack = []
        while tree_root or stack:
            if tree_root:
                stack.append(tree_root)
                tree_root = tree_root.left
            else:
                node = stack.pop()
                print(node.value)
                tree_root = node.right
    
    @staticmethod
    def postorder(tree_root):
        '''
        left -> right -> root
        '''
        stack_node = []
        stack_time = []
        while tree_root or stack_node:
            if tree_root:
                stack_node.append(tree_root)
                stack_time.append(0)
                tree_root = tree_root.left
            else:
                t = stack_time.pop()
                # first time visit node
                if t == 0:
                    node = stack_node.pop()
                    stack_time.append(1)
                    tree_root = node.right
                    stack_node.append(node)
                else:
                    node = stack_node.pop()
                    print(node.value)
                    tree_root = None

在非递归版本中，由于要回退访问已访问的节点，所以我们借助栈来保存节点。
tips：在后序遍历中，当栈内节点第二次被访问时，此时其左右节点才完成遍历，该节点才能完全出栈。

按层访问
前面的三种遍历都是深度优先，有时需要广度优先进行遍历，即按层访问。

@staticmethod
    def level_order(tree_root):
        '''
        层次遍历
        '''
        from collections import deque
        deq = deque()
        deq.append(tree_root)
        while deq:
            node = deq.popleft()
            print(node.value)
            if node.left:
                deq.append(node.left)
            if node.right:
                deq.append(node.right)

重建二叉树
根据不同的遍历结果重建二叉树。其中只根据中序遍历结果，对应二叉树的形式为多解。

@staticmethod
    def create_tree_by_preorder(L):
        '''
        前序遍历结果重构二叉树，其中 left < root < right
        '''
        if not L:
            return
        
        root = BTree(L[0])
        # 当前节点非叶子节点
        if len(L) > 1:
            i = 1
            while L[i] < L[0]:
                i += 1

            if i > 0:
                root.left = BTree.create_tree_by_preorder(L[1: i])
            if i < len(L):
                root.right = BTree.create_tree_by_preorder(L[i:])
        
        return root
    
    @staticmethod
    def create_tree_by_postorder(L):
        '''
         后序遍历结果重构二叉树，其中left < root < right
        '''
        if not L:
            return
        
        root = BTree(L[-1])
        
        if len(L) > 1:
            i = 1
            while L[i] < L[-1]:
                i += 1
            
            root.left = BTree.create_tree_by_postorder(L[:i])
            
            if i < len(L) - 1:
                root.right = BTree.create_tree_by_postorder(L[i:])
        
        return root

判断树是否相同
判断两颗树是否相同

@staticmethod
    def is_btree_equal(tree_root1, tree_root2):
        if not tree_root1 and not tree_root2:
            return True
        
        if tree_root1.value != tree_root2.value:
            return False
        
        return BTree.is_btree_equal(tree_root1.left, tree_root2.left) and BTree.is_btree_equal(tree_root1.right, tree_root2.right)
                    

count
计算节点数和层数

@staticmethod
    def count_node(tree_root):
        if not tree_root:
            return 0
        
        return 1 + BTree.count_node(tree_root.left) + BTree.count_node(tree_root.right)

@staticmethod
    def get_level(tree_root):
        if not tree_root:
            return 0
        return 1 + max(BTree.get_level(tree_root.left), BTree.get_level(tree_root.right))