深入理解二叉树的前中后序

ゝ一世哀愁。 2024-04-01 11:10 17阅读 0赞

#### 一、问题 ####

二叉树的前中后序遍历到底是什么，仅仅是三个顺序不同的 List 吗？为什么多叉树没有中序遍历？

#### 二、遍历框架 ####

所谓二叉树遍历是按某种特定规则，依次对二叉树中的节点进行相应的操作，**并且每个节点只操作一次**。

二叉树遍历的递归框架如下

void traverse(TreeNode* root) {
        if (root == nullptr) {
            return;
        }
        // 前序位置
        traverse(root->left);
        // 中序位置
        traverse(root->right);
        // 后序位置
    }

先不管所谓前中后序，单看 `traverse` 函数，你说它在做什么事情？

其实它就是一个能够遍历二叉树所有节点的一个函数，和你遍历数组或者链表本质上没有区别：

/* 迭代遍历数组 */
    void traverse(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
    
        }
    }
    
    /* 递归遍历数组 */
    void traverse(int[] arr, int i) {
        if (i == arr.length) {
            return;
        }
        // 前序位置
        traverse(arr, i + 1);
        // 后序位置
    }
    
    /* 迭代遍历单链表 */
    void traverse(ListNode* head) {
        for (ListNode* p = head; p != nullptr; p = p->next) {
    
        }
    }
    
    /* 递归遍历单链表 */
    void traverse(ListNode* head) {
        if (head == nullptr) {
            return;
        }
        // 前序位置
        traverse(head->next);
        // 后序位置
    }

单链表和数组的遍历可以是迭代的，也可以是递归的，**二叉树这种结构无非就是二叉链表**，由于没办法简单改写成迭代形式，所以一般说二叉树的遍历框架都是指递归的形式。

你也注意到了，只要是递归形式的遍历，都可以有前序位置和后序位置，分别在递归之前和递归之后。

![9bd76663f0164ab7b93531f916fd09ca.png][]

**所谓前序位置，就是刚进入一个节点（元素）的时候，后序位置就是即将离开一个节点（元素）的时候**，那么进一步，你把代码写在不同位置，代码执行的时机也不同。

比如说，如果让你**倒序打印**一条单链表上所有节点的值，你怎么搞？

实现方式当然有很多，但如果你对递归的理解足够透彻，可以利用后序位置来操作：

/* 递归遍历单链表，倒序打印链表元素 */
    void traverse(ListNode* head) {
        if (head == nullptr) {
            return;
        }
        traverse(head.next);
        // 后序位置
        print(head.val);
    }

前序位置的代码在刚刚进入一个二叉树节点的时候执行；

后序位置的代码在将要离开一个二叉树节点的时候执行；

中序位置的代码在一个二叉树节点左子树都遍历完，即将开始遍历右子树的时候执行。

#### 三、关于后续遍历 ####

前序位置是刚刚进入节点的时刻，后序位置是即将离开节点的时刻。

但这里面大有玄妙，意味着前序位置的代码只能从函数参数中获取父节点传递来的数据，而后序位置的代码不仅可以获取参数数据，还可以获取到子树通过函数返回值传递回来的数据。

举具体的例子，现在给你一棵二叉树，我问你两个简单的问题：

1、如果把根节点看做第 1 层，如何打印出每一个节点所在的层数？

2、如何打印出每个节点的左右子树各有多少节点？

第一个问题可以这样写代码：

// 二叉树遍历函数
    void traverse(TreeNode root, int level) {
        if (root == null) {
            return;
        }
        // 前序位置
        printf("节点 %s 在第 %d 层", root, level);
        traverse(root.left, level + 1);
        traverse(root.right, level + 1);
    }
    
    // 这样调用
    traverse(root, 1);

第二个问题可以这样写代码：

// 定义：输入一棵二叉树，返回这棵二叉树的节点总数
    int count(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftCount = count(root.left);
        int rightCount = count(root.right);
        // 后序位置
        printf("节点 %s 的左子树有 %d 个节点，右子树有 %d 个节点",
                root, leftCount, rightCount);
    
        return leftCount + rightCount + 1;
    }

这两个问题的根本区别在于：一个节点在第几层，你从根节点遍历过来的过程就能顺带记录；而以一个节点为根的整棵子树有多少个节点，你需要遍历完子树之后才能数清楚。

结合这两个简单的问题，你品味一下后序位置的特点，只有后序位置才能通过返回值获取子树的信息。

**那么换句话说，一旦你发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了**

#### 四、实践 ####

Leetcode617:给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

![2dbfd17e11e64091a3b42c21a7ed9308.png][]

输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
    输出：[3,4,5,5,4,null,7]

可以使用深度优先搜索合并两个二叉树。从根节点开始同时遍历两个二叉树，并将对应的节点进行合并。

class Solution {
    public:
        TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
            if (t1 == nullptr) {
                return t2;
            }
            if (t2 == nullptr) {
                return t1;
            }
            auto merged = new TreeNode(t1->val + t2->val);
            merged->left = mergeTrees(t1->left, t2->left);
            merged->right = mergeTrees(t1->right, t2->right);
            return merged;
        }
    };

参考：

[力扣][Link 1]  
[东哥带你刷二叉树（纲领篇） :: labuladong的算法小抄][_ labuladong]

[9bd76663f0164ab7b93531f916fd09ca.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/3b01a9358a014868b2bdd9ee92e6ed5e.png
[2dbfd17e11e64091a3b42c21a7ed9308.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/b68031569e6a4287b95f9285904057e1.png
[Link 1]: https://leetcode.cn/problems/merge-two-binary-trees/solution/he-bing-er-cha-shu-by-leetcode-solution/
[_ labuladong]: https://labuladong.github.io/algo/2/21/36/