LeetCode | 力扣 | 难度 |
🟢 | ||
🟢 | ||
🟢 | ||
- | 🟢 |
一 二叉树的前中后序遍历
前中后序遍历框架
void traverse(TreeNode root) { if (root == null) { return; } // 前序位置 traverse(root.left); // 中序位置 traverse(root.right); // 后序位置 }
执行逻辑：
前序位置的代码在刚刚进入一个二叉树节点的时候执行；
后序位置的代码在将要离开一个二叉树节点的时候执行；
中序位置的代码在一个二叉树节点左子树都遍历完，即将开始遍历右子树的时候执行。
二叉树的所有问题，就是让你在前中后序位置注入巧妙的代码逻辑，去达到自己的目的，你只需要单独思考每一个节点应该做什么，其他的不用你管，抛给二叉树遍历框架，递归会在所有节点上做相同的操作。
二 两种解题方法
遇到一道二叉树的题目时的通用思考过程是：
1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个
traverse 函数配合外部变量来实现。自顶向下，一般需要一个外部的数据来进行记录。
2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值。
自低向上
无论使用哪一种思维模式，你都要明白二叉树的每一个节点需要做什么，需要在什么时候（前中后序）做。
举具体的例子，现在给你一棵二叉树，我问你两个简单的问题：
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; }
这两个问题的根本区别在于：一个节点在第几层，你从根节点遍历过来的过程就能顺带记录，用递归函数的参数就能传递下去；而以一个节点为根的整棵子树有多少个节点，你需要遍历完子树之后才能数清楚，然后通过递归函数的返回值拿到答案。
结合这两个简单的问题，你品味一下后序位置的特点，只有后序位置才能通过返回值获取子树的信息。
那么换句话说，一旦你发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了。
二叉搜索树：所有左子树所有节点均小于根节点，所有的右子树节点均大于根节点，特点为中序遍历为一个递增的数组。