树相关知识点--零碎笔记

深入理解前中后序

1. 二叉树的前中后序遍历是什么？

1. 前中后序遍历，即二叉树结构的前中后位置

1. 前序遍历-即刚刚进入一个节点的时候
2. 中序遍历-即进入节点之后未离开节点之前
3. 后序遍历-即即将离开第一个节点的时候

2. 前中后序是遍历二叉树过程中处理每一个节点的三个特殊时间点

1. 前--刚刚进入一个二叉树节点的时候执行
2. 后--将要离开一个二叉树节点的时候执行
3. 中--在一个二叉树左子树遍历完，即将开始遍历右子树的时候执行

2. 后序遍历有什么特殊之处？

1. 前序位置的代码只能从函数参数中获取父节点传递来的数据
2. 后序位置的代码不仅可以获取参数数据，还可以获取到子树通过函数返回值传递回来的数据 1.

3. 为什么多叉树没有中序号遍历？

1. 在二叉树中每一个节点都只会进行唯一一次左右子树的切换
2. 多叉树可能有很多个子节点，会多次切换子树去遍历
3. 因此多叉树节点没有唯一的中序遍历位置

二叉树问题本质

二叉树的所有问题，就是在前中后序位置注入巧妙的代码逻辑，从而达到目的。因此只需要单独思考每一个节点应该做什么即可，其他交给二叉树的遍历框架，递归会在所有的节点上做相同的操作。

解题思路

1. 二叉树题目的递归解法可以分为两类思路

1. 第一类：遍历一遍二叉树得出答案，即回溯算法核心框架
2. 第二类：通过分解问题计算出答案，即动态规划核心框架

2. 是否可以通过遍历一遍二叉树得到答案
3. 是否可以定义一个递归函数，通过子问题（子树）的答案推倒出原问题的答案？

1. 如果可以，仔细思考如何定义递归函数

中序遍历的重要性

1. 中序遍历按照左根右的顺序进行遍历
2. 遍历出来的数据具有非递减的性质，相当于遍历有序数组

后序遍历的特殊之处

1. 前序位置的代码只能从函数参数中获取父节点传递来的数据
2. 后序位置代码不仅可以获取参数数据，还可以获取到子树通过返回值传递回来的数据
3. 使用例题说明

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

void traverse(TreeNode root, int level) {
    if(root == null) {
        return;
    }

    // 前序位置
    System.out.println("节点 " + 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);

	// 后序位置
	System.out.println(leftCount);
	System.out.println(rightCount);

	return leftCount + rightCount + 1;
}

• a b两个问题的区别

• 一个节点在第几层，从根节点遍历过来的时候就能够知道，因为遍历过程中就能顺带记录
• 以一个节点为根的整颗子树有多少个节点，需要遍历完子树才能够清楚，通过递归函数的返回值拿到答案

• 所以，面对问题的时候，要仔细分析问题解是否和子问题相关还是可以直接通过遍历得到结果

值得注意的点

1. 如果可以，尽量使用没有返回值的函数作为递归函数

1. 这样做会减少额外空间的使用

2. 思考如何精简判断逻辑，会使代码变得更加简洁易懂

参考

https://labuladong.github.io/algo/di-ling-zh-bfe1b/dong-ge-da-334dd/