theme: orange

二叉树的递归性质

“二叉树”这个概念本身就是可以用递归的形式进行定义的：

二叉树的递归定义

1. 一个二叉树可以是空树，即它不包含任何节点。
2. 一个非空的二叉树由一个根节点和两个子树组成：

• 左子树本身是一个二叉树。
• 右子树本身也是一个二叉树。

这种定义方式强调了二叉树在结构上的递归性质：二叉树可以看作是一个根节点加上两棵子树（左子树和右子树），而这两棵子树本身也是二叉树。

递归性质使得我们能够将复杂的问题分解为更小的、相似的子问题。通过递归地解决这些子问题，我们可以逐步构建出整个问题的解决方案。

在二叉树中，这种分解通常表现为将某个与以V为根的子树相关的问题，转化为与V的左子树和V的右子树相关的问题。

• V的左子树和V的右子树也是二叉树，并且它们相比于以V为根的子树规模更小
• 所以这是将一个规模较大的问题转换为规模较小的相似的子问题的过程，是典型的“分治”思想
• 基本问题一般对应于“空树”或“只有一个节点的子树”，此时问题可以直接求解

基于二叉树的递归性质解决遍历问题

遍历问题的递归分解

对二叉树的遍历问题进行递归分解：

对以V为根的子树的遍历，可以转化为：

• 对节点V的访问
• 遍历V的左子树
• 遍历对V的右子树

基本问题：当遇到空树时不用遍历直接返回

前序、中序和后序遍历

根据节点v的访问时机，遍历又可以分为：前序、中序和后序遍历。

代码实现（递归）

我们可以很容易地实现用递归函数实现二叉树的遍历。

前序遍历

// 前序遍历以v为根的子树
public void preorder_recur(TreeNode v){
    /* 递归终点 */
    if(v == null) return;
    
    /* 分治过程 */
    visit(v);                // 访问节点v
    preorder_recur(v.left);  // 遍历v的左子树
    preorder_recur(v.right); // 遍历v的右子树
}

中序遍历

// 中序遍历以v为根的子树
public void preorder_recur(TreeNode v){
    /* 递归终点 */
    if(v == null) return;
    
    /* 分治过程 */
    preorder_recur(v.left);  // 遍历v的左子树
    visit(v);                // 访问节点v
    preorder_recur(v.right); // 遍历v的右子树
}

后序遍历

// 后序遍历以v为根的子树
public void preorder_recur(TreeNode v){
    /* 递归终点 */
    if(v == null) return;
    
    /* 分治过程 */
    preorder_recur(v.left);  // 遍历v的左子树
    preorder_recur(v.right); // 遍历v的右子树
    visit(v);                // 访问节点v
}

代码实现（递归转迭代：手动模拟递归调用栈）

参考文章：知乎-xxChan：递归改写成迭代的通用方法——妈妈再也不用担心我不会写二叉树非递归遍历了

使用通用的递归转迭代方法（手动模拟递归调用栈），可以将遍历的递归实现转换成迭代实现。

函数的调用过程是如何实现的？

如果在函数a的执行过程中调用了其他函数（记为函数b），就需要先将函数a的当前运行状态保存下来（保存现场），然后转去执行函数b。等函数b执行结束后，再回过头来根据之前保存的函数a的断点处运行状态继续执行函数a。

在计算机中，函数的调用过程是通过函数调用栈来实现的。用栈帧记录每一个函数运行时的状态信息，包括参数的值、局部变量的值以及当前执行到的位置（程序计数器PC的值）。每当发生函数调用时，就创建一个栈帧并压入栈顶，随着函数的执行同步更新栈帧中的内容。如果某个函数执行结束，就将它的栈帧从栈中弹出。

当函数a将要执行函数b的调用语句时，此时栈顶还是函数a的栈帧，并且同步记录者函数a的当前运行状态。当函数a执行到函数b的调用语句时，函数b的栈帧会压入栈顶，接下来开始函数b的执行。执行完函数b之后，将函数b的栈帧弹出，此时栈顶又变成了函数a的栈帧。这时我们就可以从函数a的栈帧中读取它在调用函数b之前的运行状态，然后就可以继续执行函数a了。

手动模拟递归调用栈

以中序遍历为例，下面是中序遍历的递归实现代码：

// 中序遍历以v为根的子树
public void preorder_recur(TreeNode v){
    /* 递归终点 */
    if(v == null) return;    // pc = 0
    
    /* 分治过程 */
    preorder_recur(v.left);  // pc = 1
    visit(v);                // pc = 2
    preorder_recur(v.right); // pc = 3
                             // pc = 4
}

在函数preorder_recur(v)中：

1. 递归调用函数preorder_recur(v.left)
2. 返回preorder_recur(v)函数中，对节点v进行访问
3. 递归调用函数preorder_recur(v.right)

首先，我们需要定义一个用于表示栈帧的数据结构StackFrame。

class Frame {
    TreeNode node; // 递归函数的参数
    int pc;        // 下一条要执行的语句

    public Frame(TreeNode node, int pc){
        this.node = node; 
        this.pc = pc;     
    }
}

下面给出中序遍历的迭代实现：

public void inorder_iter1(TreeNode root) {
    Deque<Frame> stack = new LinkedList<>(); // 函数调用栈

    stack.push(new Frame(root, 0));

    while(!stack.isEmpty()){
        Frame curFrame = stack.peek();

        switch(curFrame.pc){
            case 0: {
                        if(curFrame.node == null){
                            stack.pop(); 
                        }else{
                            curFrame.pc = 1;
                        }
                        break;
                    }
            case 1: {
                        stack.push(new Frame(curFrame.node.left, 0));
                        curFrame.pc = 2;
                        break;
                    }
            case 2: {
                        visit(curFrame.node);
                        curFrame.pc = 3;
                        break;
                    }
            case 3: {
                        stack.push(new Frame(curFrame.node.right, 0));
                        curFrame.pc = 4;
                        break;
                    }
            case 4: {
                        stack.pop();
                        break;
                    }
        }
    }
}

在上述代码中，当curFrame.pc == 3时，已经到了当前函数的最后一行preorder_recur(v.right)，当preorder_recur(v.right)执行完返回之后，已经没有需要执行的语句了。因此可以在将新函数的栈帧压栈前，就将当前函数的栈帧弹出，即将case 3和case 4合并为：

case 3: {
            stack.pop();
            stack.push(new Frame(curFrame.node.right, 0));
            // curFrame.pc = 4;
            break;
        }

除此之外，在case 0中，也不必先将curFrame.pc赋值为1，然后再进入一次循环判断curFrame.pc == 1后执行case 1的内容。可以直接将case 1的内容提前到赋值语句curFrame.pc = 1处：

case 0: {
            if(curFrame.node == null){
                stack.pop(); 
            }else{
                // curFrame.pc = 1;
                stack.push(new Frame(curFrame.node.left, 0));
                curFrame.pc = 2;    
            }
            break;
        }
// case 1: {
//             stack.push(new Frame(curFrame.node.left, 0));
//             curFrame.pc = 2;
//             break;
//         }

同理，可以直接将case 3的内容提前到赋值语句curFrame.pc = 2处：

case 2: {
            result.add(curFrame.node.val);
            // curFrame.pc = 3;
            stack.pop();
            stack.push(new Frame(curFrame.node.right, 0));
            break;
        }

此时只剩下case 0和case 2了，既然是一个2值，我们不妨用一个布尔变量来存，用False来代表case 0、用True来代表case 2：

public void inorder_iter1(TreeNode root) {
    List<Integer> result = new LinkedList<>();

    Deque<Frame> stack = new LinkedList<>();
    stack.push(new Frame(root, false));

    while(!stack.isEmpty()){
        Frame curFrame = stack.peek();

        if(curFrame.pc == false){
            if(curFrame.node == null){
                stack.pop(); 
            }else{
                stack.push(new Frame(curFrame.node.left, false));
                curFrame.pc = true;    
            }
        }else{
            visit(curFrame.node);
            stack.pop();
            stack.push(new Frame(curFrame.node.right, false));
        }
    }
}