二叉树的递归如何写

大家好，我是三叔，很高兴这期又和大家见面了，一个奋斗在互联网的打工人。

笔者在一文读懂二叉树中有介绍到二叉树的深度优先搜索中讲到：前序遍历、中序遍历、后续遍历，今天我就用代码的形式给大家展示出来。

首先大家需要了解递归的原理

递归的底层实现

递归遍历的底层原理涉及到函数调用栈的概念。当一个函数在递归调用自身时，每一次递归调用都会创建一个新的函数调用帧并将其压入函数调用栈中。当递归调用结束时，对应的函数调用帧会从栈中弹出，恢复到上一次的函数调用点，然后继续执行后续的代码。

对于二叉树的递归遍历（如前序遍历、中序遍历、后序遍历），递归函数的基本思想是：

在每一次递归调用中，首先处理当前节点。
然后递归调用自身来处理当前节点的左子树。
最后递归调用自身来处理当前节点的右子树。

递归遍历的过程可以理解为对树进行深度优先搜索（DFS）。当递归到达叶子节点（没有子节点）时，递归调用会返回到上一层，并继续处理上一层节点的右子树（如果存在）。

在底层实现中，每一次递归调用会将当前节点的信息（如引用或指针）和其他必要的状态（如遍历的进度、临时变量等）保存在函数调用帧中。这些帧按照调用顺序存储在函数调用栈中。

递归遍历的结束条件通常是当当前节点为空（null）时，即遍历到了树的底部。在这种情况下，递归调用会返回到上一层，并继续处理上一层的右子树或结束整个遍历过程。

需要注意的是，递归遍历可能导致函数调用栈的深度增加，因此在处理大规模树或深度嵌套的情况下，可能会面临栈溢出的风险。为了避免这种情况，可以使用迭代的方式替代递归实现。

二叉树的前序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
 // 力扣的#144题
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();// 构造一个List返回
        traversalPrev(root, result);// 递归方法
        return result;

    }

    private void traversalPrev(TreeNode root, List<Integer> result) {
    	// 当前遍历的节点一直到最底部，当左右孩子或者根节点为null的时候，结束循环，退出递归
    	// 这里很重要，如果没有准确的掌握递归结束的条件，很容易就会造成栈溢出
        if(root == null) {
            return;
        }
        // 前序遍历 中左右
        result.add(root.val);
        traversalPrev(root.left, result);
        traversalPrev(root.right, result);
    }
}

二叉树的中序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
 // 力扣#94
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        traveraslMid(root, result);
        return result;
    }
	// 中序遍历的递归
    private void traveraslMid(TreeNode root, List<Integer> result) {
        if(root == null) {
            return ;
        }
        // 中序遍历：左中右
        traveraslMid(root.left, result);
        result.add(root.val);
        traveraslMid(root.right, result);
    }
}

二叉树的后序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
 // 力扣145
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        traversalAfter(root, result);
        return result;
    }

    private void traversalAfter(TreeNode root, List<Integer> result) {
        if(root == null) {
            return ;
        }
        traversalAfter(root.left, result);// 左
        traversalAfter(root.right, result);// 右
        result.add(root.val);// 中
    }
}