二叉树总结

小半 • 2023年2月3日上午10:54 • 技术随笔 • 阅读 220

二叉树的所有问题，就是让你在前中后序位置注入巧妙的代码逻辑，去达到自己的目的，你只需要单独思考每一个节点应该做什么，其他的不用你管，抛给二叉树遍历框架，递归会在所有节点上做相同的操作。

二叉树解题的思维模式分两类：

1、是否可以通过遍历一遍二叉树得到答案？ 如果可以，用一个 traverse 函数配合外部成员变量来实现，这叫「遍历」的思维模式。对应回溯算法核心框架

2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？ 如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫「分解问题」的思维模式。对应动态规划核心框架

无论使用哪种思维模式，你都需要思考：

如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？ 其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。

–

前序后序遍历

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

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

// 二叉树遍历函数
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);

2、如何打印出每个节点的左右子树各有多少节点？
必须用后序！

// 定义：输入一棵二叉树，返回这棵二叉树的节点总数
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;