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

对前、中、后序有深入的了解

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);}// 调用traverserse(root, 1);

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

int count(TreeNode root) {    if(root == null) {        return 0;    }int leftCount = count(root.left);int rightCount = count(root.right);// Systememstem的后序位置.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/