树的知识以及示例代码

本文对树相关的知识进行梳理，并给出示例代码或者代码模板，方便以后解题。

一些定义

二叉树

二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。树的问题很多都可以由广度优先搜索或深度优先搜索解决。

二叉搜索树（Binary Search Tree）

它或者是一棵空树，或者是具有下列性质的二叉树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉搜索树。

遍历相关

注意点

以根访问顺序决定是什么遍历
左子树都是优先右子树

前序遍历

前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。（从上到下）

中序遍历

中序遍历是先遍历左子树，然后访问根节点，然后遍历右子树。对于二叉搜索树，我们可以通过中序遍历得到一个递增的有序序列。

后序遍历

后序遍历是先遍历左子树，然后遍历右子树，最后访问树的根节点。

当你删除树中的节点时，删除过程将按照后序遍历的顺序进行。也就是说，当你删除一个节点时，你将首先删除它的左节点和它的右边的节点，然后再删除节点本身。

层序遍历

层序遍历就是逐层遍历树结构。广度优先搜索是一种广泛运用在树或图这类数据结构中，遍历或搜索的算法。该算法从一个根节点开始，首先访问节点本身。然后遍历它的相邻节点，其次遍历它的二级邻节点、三级邻节点，以此类推。通常，我们使用一个叫做队列的数据结构来帮助我们做广度优先搜索。

BFS，广度/宽度优先。其实就是从上到下，先把每一层遍历完之后再遍历一下一层。使用Queue的数据结构。我们将root节点初始化进队列，通过消耗尾部，插入头部的方式来完成BFS。

运用递归解决树的问题

树可以以递归的方式定义为一个节点（根节点），它包括一个值和一个指向其他节点指针的列表。递归是树的特性之一。因此，许多树问题可以通过递归的方式来解决。对于每个递归层级，我们只能关注单个节点内的问题，并通过递归调用函数来解决其子节点问题。

“自顶向下” 的解决方案

“自顶向下” 意味着在每个递归层级，我们将首先访问节点来计算一些值，并在递归调用函数时将这些值传递到子节点。所以 “自顶向下” 的解决方案可以被认为是一种前序遍历。

“自底向上” 的解决方案

“自底向上” 是另一种递归方法。在每个递归层次上，我们首先对所有子节点递归地调用函数，然后根据返回值和根节点本身的值得到答案。这个过程可以看作是后序遍历的一种。

二叉树解题策略

一递归
二队列 + 迭代（层次遍历）
三栈 + 迭代（非递归遍历）
四其它

三种基本的遍历方式，都可以用递归来实现。写递归算法的时候，需要注意递归退出条件以及递归操作的表达。

示例代码

二叉搜索树插入操作：从根节点开始，若插入的值比根节点的值小，则将其插入根节点的左子树；若比根节点的值大，则将其插入根节点的右子树。该操作可使用递归进行实现。

def insert(self, root, val):
        '''二叉搜索树插入操作'''
        if root == None:
            root = TreeNode(val)
        elif val < root.val:
            root.left = self.insert(root.left, val)
        elif val > root.val:
            root.right = self.insert(root.right, val)
        return root

二叉搜索树的查询操作：从根节点开始查找，待查找的值是否与根节点的值相同，若相同则返回True；否则，判断待寻找的值是否比根节点的值小，若是则进入根节点左子树进行查找，否则进入右子树进行查找。该操作使用递归实现。

def query(self, root, val):
        '''二叉搜索树查询操作'''
        if root == None:
            return False
        if root.val == val:
            return True
        elif val < root.val:
            return self.query(root.left, val)
        elif val > root.val:
            return self.query(root.right, val)

查找二叉搜索树中的最大（小值）

查找最小值：从根节点开始，沿着左子树一直往下，直到找到最后一个左子树节点，按照定义可知，该节点一定是该二叉搜索树中的最小值节点。

def findMin(self, root):
        '''查找二叉搜索树中最小值点'''
        if root.left:
            return self.findMin(root.left)
        else:
            return root

查找最大值：从根节点开始，沿着右子树一直往下，直到找到最后一个右子树节点，按照定义可知，该节点一定是该二叉搜索树中的最大值节点。

def findMax(self, root):
        '''查找二叉搜索树中最大值点'''
        if root.right:
            return self.findMax(root.right)
        else:
            return root

二叉搜索树删除节点操作

def delNode(self, root, val):
        '''删除二叉搜索树中值为val的点'''
        if root == None:
            return 
        if val < root.val:
            root.left = self.delNode(root.left, val)
        elif val > root.val:
            root.right = self.delNode(root.right, val)
        # 当val == root.val时，分为三种情况：只有左子树或者只有右子树、有左、右子树、即无左子树又无右子树
        else:
            if root.left and root.right:
                # 既有左子树又有右子树，则需找到右子树中最小值节点
                temp = self.findMin(root.right)
                root.val = temp.val
                # 再把右子树中最小值节点删除
                root.right = self.delNode(root.right, temp.val)
            elif root.right == None and root.left == None:
                # 左右子树都为空
                root = None
            elif root.right == None:
                # 只有左子树
                root = root.left
            elif root.left == None:
                # 只有右子树
                root = root.right
        return root

二叉搜索树打印操作：实现二叉搜索树的中序遍历，并打印出来。该方法打印出来的数列将是按照递增顺序排列。

def printTree(self, root):
        # 打印二叉搜索树(中序打印，有序数列)
        if root == None:
            return 
        self.printTree(root.left)
        print(root.val, end = ' ')
        self.printTree(root.right)

验证二叉搜索树

def isValidBST(self, root):
        
        if root is None:
            return True
        
        s = [(root, float('-inf'), float('inf'))]
        while len(s) > 0:
            node, low, up = s.pop()
            if node.left is not None:
                if node.left.val <= low or node.left.val >= node.val:
                    return False
                s.append((node.left, low, node.val))
            if node.right is not None:
                if node.right.val <= node.val or node.right.val >= up:
                    return False
                s.append((node.right, node.val, up))
        return True

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。保证原始二叉搜索树中不存在新值。

def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        
        if root is None:
            return TreeNode(val)
        
        if val > root.val:
            root.right = self.insertIntoBST(root.right, val)
        else:
            root.left = self.insertIntoBST(root.left, val)
        
        return root

给定一个二叉树，判断它是否是高度平衡的二叉树。

def isBalanced(self, root: TreeNode) -> bool:
        
        # post-order iterative
        
        s = [[TreeNode(), -1, -1]]
        node, last = root, None
        while len(s) > 1 or node is not None:
            if node is not None:
                s.append([node, -1, -1])
                node = node.left
                if node is None:
                    s[-1][1] = 0
            else:
                peek = s[-1][0]
                if peek.right is not None and last != peek.right:
                    node = peek.right
                else:
                    if peek.right is None:
                        s[-1][2] = 0
                    last, dl, dr = s.pop()
                    if abs(dl - dr) > 1:
                        return False
                    d = max(dl, dr) + 1
                    if s[-1][1] == -1:
                        s[-1][1] = d
                    else:
                        s[-1][2] = d
        
        return True

递归模板

递归实现二叉树遍历非常简单，不同顺序区别仅在于访问父结点顺序

前序遍历先访问根节点，再前序遍历左子树，再前序遍历右子树

def preorder_rec(root):
    if root is None:
        return
    visit(root)
    preorder_rec(root.left)
    preorder_rec(root.right)
    return

def inorder_rec(root):
    if root is None:
        return
    inorder_rec(root.left)
    visit(root)
    inorder_rec(root.right)
    return

def postorder_rec(root):
    if root is None:
        return
    postorder_rec(root.left)
    postorder_rec(root.right)
    visit(root)
    return

本质上是图的DFS的一个特例，因此可以用栈来实现

# 前序非递归
    def preorderTraversal(self, root) :
        preorder = []
        if root is None:
            return preorder
        
        stack = [root]
        while len(stack) > 0:
            node = stack.pop()
            preorder.append(node.val)
            if node.right is not None:
                stack.append(node.right)
            if node.left is not None:
                stack.append(node.left)
        
        return preorder

# 中序非递归
def inorderTraversal(self, root):
    stack, inorder = [], []
    node = root
    while len(stack) > 0 or node is not None:
        if node is not None:
            stack.append(node)
            node = node.left
        else:
            node = stack.pop()
            inorder.append(node.val)
            node = node.right
    return inorder


    # 后序非递归
    def postorderTraversal(self, root):
        s, postorder = [], []
        node, last_visit = root, None
        
        while len(s) > 0 or node is not None:
            if node is not None:
                s.append(node)
                node = node.left
            else:
                peek = s[-1]
                if peek.right is not None and last_visit != peek.right:
                    node = peek.right
                else:
                    last_visit = s.pop()
                    postorder.append(last_visit.val)
        
        
        return postorder

核心就是：根节点必须在右节点弹出之后，再弹出

二叉树算法的设计的总路线：明确一个节点要做的事情，然后剩下的事抛给框架。

def traverse(root):
    // root 需要做什么？在这做。

    // 其他的不用 root 操心，抛给框架
    traverse(root.left)
    traverse(root.right)

如何把二叉树所有的节点中的值加一？

def plusOne(root):
    if not root: return None
    root.val += 1
    plusOne(root.left)
    plusOne(root.right)

DFS模板

DFS 深度搜索-从下向上（分治法）

def preorderTraversal(self, root):
    if root is None:
        return []
    
    left_result = self.preorderTraversal(root.left)
    right_result = self.preorderTraversal(root.right)
    
    return [root.val] + left_result + right_result

DFS 深度搜索（从上到下）和分治法区别：前者一般将最终结果通过指针参数传入，后者一般递归返回结果最后合并

# BFS 层次遍历
def levelOrder(self, root: TreeNode):
    from collections import deque    
    levels = []
    if root is None:
        return levels
    
    bfs = deque([root])
    
    while len(bfs) > 0:
        levels.append([])
        
        level_size = len(bfs)
        for _ in range(level_size):
            node = bfs.popleft()
            levels[-1].append(node.val)
            
            if node.left is not None:
                bfs.append(node.left)
            if node.right is not None:
                bfs.append(node.right)
    
    return levels

在递归中，如果层级过深，我们很可能保存过多的临时变量，导致栈溢出。函数调用的参数是通过栈空间来传递的，在调用过程中会占用线程的栈资源。而递归调用，只有走到最后的结束点后函数才能依次退出，而未到达最后的结束点之前，占用的栈空间一直没有释放，如果递归调用次数过多，就可能导致占用的栈资源超过线程的最大值，从而导致栈溢出，导致程序的异常退出。

99%的递归转非递归，都可以通过栈来进行实现。