算法与数据结构-二叉树

二叉树的定义，来自leetcode，下面都用python来实现

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

二叉树的层次遍历，有BFS和DFS两种

leetcode 102,103,107

BFS与图的广度优先遍历一致，使用队列
class Solution(object):
# bfs iterative
    def levelOrder(self,root):
        if not root:
            return []
        quene = []
        quene.append(root)
        res = []
        depth = 0
        while quene:
            index = quene.pop(0)
            res.append(index.val)
            if index.left:
                quene.append(index.left)
            if index.right:
                quene.append(index.right)  
        return res

DFS遍历基于先序遍历（其他两种也可以），因为都可以保证左节点在右节点前面进入结果列表
# dfs Recusive
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        res = [[]]
        self.preorder(root,res,0)
        return res
        
    def preorder(self,r,res,depth):
        if depth > len(res)-1:
            res.append([])
        res[depth].append(r.val)
        if r.left:
            self.preorder(r.left,res,depth+1)
        if r.right:
            self.preorder(r.right,res,depth+1)
        

扩展：判断一棵树是否是完全二叉树

完全二叉树即一个数除了最后一层之上的层都是满节点的，最后一层左边是满的
如

          1
        2      3 
     4   5    7   8
  9 10 11 None None None None None

则将每个节点的左右子节点如果为NULL都补成一个特殊元素如#，在层次遍历输出，则如果是完全二叉树这个特殊元素都在输出列表的最后

---

二叉树的先序，中序，后序遍历（非递归）

递归的忽略不讲，非递归的实现：先序和中序都基于栈（因为是基于backtracking回溯的思想）

# 先序，相当于用栈一直入左子节点，同时打印每个根节点的值，遇到左边为空时候回溯，此时添加右子节点

    def pre_order_by_stack(self,r):
        if not r:
            return
        myStack = []
        node = r
        while node or myStack:
            while node:
                print(node.root)
                myStack.append(node)
                node = node.left
            node = myStack.pop()
            node = node.right

# 中序，与先序基本同理，回溯时再打印节点，这样保证顺序是左根右
    def in_order_by_stack(self,r):
        if not r:
            return
        myStack = []
        node = r
        while node or myStack:
            while node:
                myStack.append(node)
                node = node.left
            node = myStack.pop()
            print(node.root)
            node = node.right
后序：先打印出栈节点，再添加左右子节点，最后将打印结果倒转，较难理解，可以背答案。
def post_order(self,r):
        if not r:
            return
        myStack = []
        res = []
        node = r  
        myStack.append(node)
        while myStack:
            node = myStack.pop()
            res.append(node.root)
            if node.left is not None:
                myStack.append(node.left)
            if node.right is not None:
                myStack.append(node.right)
        res.reverse()
        return res

---

二叉查找树

重建二叉树

105. Construct Binary Tree from Preorder and Inorder Traversal
     先序+中序遍历结果重建二叉树，二叉树没有重复元素

先序遍历的第一个节点肯定是根节点
然后查找这个节点的值在中序遍历结果的位置，左边的所有元素在根节点的左子树下
右边的所有元素在根节点的右子树下

class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if inorder:
            ind = inorder.index(preorder.pop(0))
            root = TreeNode(inorder[ind])
            root.left = self.buildTree(preorder,inorder[0:ind])
            root.right = self.buildTree(preorder,inorder[ind+1:])
            return root

106. Construct Binary Tree from Inorder and Postorder Traversal
     中序和后序结果重建二叉树

class Solution(object):
    def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        if postorder:
            ind = inorder.index(postorder.pop())
            root = TreeNode(inorder[ind])
            root.left = self.buildTree(inorder[:ind],postorder[:ind])#[:ind])
            root.right = self.buildTree(inorder[ind+1:],postorder[ind:])#[ind+1:])
            return root