目录
二叉树的深度优先搜索又可以细分为前序遍历、中序遍历和后序遍历。
因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。并且前中后序三种遍历的唯一区别就是访问根节点的时机不同，在做题的时候，选择一个适当的遍历顺序，对于算法的理解是非常有帮助的。
前序遍历：
前序遍历可以给左右两棵子树传递信息。
1. 二叉树的所有路径（简单）
路径以字符串形式存储，从根节点开始遍历，每次遍历时将当前节点的值加入到父节点传递的路径中，如果该节点为叶子节点，将路径存储到答案数组中。否则，将"->"加入到路径中并递归遍历该节点的左右子树。
该问题需要一个类的成员变量vector<string> ans作为答案。
重复的子问题——函数头设计
给一个节点root和它的父节点要往下传递的路径path。
void dfs(TreeNode* root, string path)
子问题在做什么——函数体设计
- 更新path：path += to_string(root->val);
- 如果是叶子结点：if (root->left == nullptr && root->right == nullptr) {ans.push_back(path); return;}
- 将"->"加入到路径中：path += "->";
- 递归左右子树：dfs(root->left, path); dfs(root->right, path);
递归出口
当前节点是空节点，直接返回。
class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
dfs(root, "");
return ans;
}
private:
void dfs(TreeNode* root, string path)
{
if (root == nullptr)
return;
path += to_string(root->val);
if (root->left == nullptr && root->right == nullptr)
{
ans.push_back(path);
return;
}
path += "->";
dfs(root->left, path);
dfs(root->right, path);
}
vector<string> ans;
};2. 求根节点到叶节点数字之和（简单）
从根节点开始遍历，每次遍历时将当前节点的值和父节点传递的值整合，如果该节点为叶子节点，将整合后的值加到答案中。否则，递归遍历该节点的左右子树。
该问题需要一个类的成员变量int ans作为答案。
重复的子问题——函数头设计
给一个节点root和它的父节点要往下传递的值num。
void dfs(TreeNode* root, int num)
子问题在做什么——函数体设计
- 更新num：num = num * 10 + root->val;
- 如果是叶子结点：if (root->left == nullptr && root->right == nullptr) {ans += num; return;}
- 递归左右子树：dfs(root->left, num); dfs(root->right, num);
递归出口
当前节点是空结点，直接返回。
class Solution {
public:
int sumNumbers(TreeNode* root) {
dfs(root, 0);
return ans;
}
private:
void dfs(TreeNode* root, int num)
{
if (root == nullptr)
return;
num = num * 10 + root->val;
if (root->left == nullptr && root->right == nullptr)
{
ans += num;
return;
}
dfs(root->left, num);
dfs(root->right, num);
}
int ans;
};3. 路径总和 III（中等）
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
节点1->节点2的路径 = 根节点->节点2的路径 - 根节点->节点1的路径
树的前缀和+回溯问题。
用path记录从根节点到当前节点的路径和（前缀和），用哈希表记录当前节点以上的出现的前缀和及出现的次数。
重复的子问题——函数头设计
给一个节点root和它的父节点要往下传递的路径path，还有targetSum。
返回值是二叉树中等于targetSum的路径数目。
int dfs(TreeNode* root, int targetSum, long long path)
子问题在做什么——函数体设计
- 更新path：path += root->val;
- 如果path-targetSum出现过，记录出现次数，没有出现过则出现次数为0：
int ans = hash.count(path - targetSum) ? hash[path - targetSum] : 0; - 当前节点的前缀和在哈希表中的值++：hash[path]++;
- 递归左右子树，把左右子树中等于targetSum的路径数目添加进答案中：
ans += dfs(root->left, targetSum, path); ans += dfs(root->right, targetSum, path); - 回溯：hash[path]--;
- 返回二叉树中等于targetSum的路径数目：return ans;
递归出口
当前节点是空结点，直接返回0。
class Solution {
public:
int pathSum(TreeNode* root, int targetSum) {
hash[0] = 1;
return dfs(root, targetSum, 0);
}
private:
int dfs(TreeNode* root, int targetSum, long long path)
{
if (root == nullptr)
return 0;
// 更新path
path += root->val;
// 如果path-targetSum出现过，记录出现次数，没有出现过则出现次数为0
int ans = hash.count(path - targetSum) ? hash[path - targetSum] : 0;
// 当前节点的前缀和在哈希表中的值++
hash[path]++;
// 递归左右子树，把左右子树中等于targetSum的路径数目添加进答案中
ans += dfs(root->left, targetSum, path);
ans += dfs(root->right, targetSum, path);
// 回溯
hash[path]--;
return ans;
}
long long path; // 从根节点到当前节点的路径和（前缀和）
unordered_map<long long, int> hash; // 记录当前节点以上的出现的前缀和及出现的次数
};中序遍历：
如果一棵树是二叉搜索树，那么它的中序遍历的结果一定是一个严格递增的序列。
1. 递增顺序搜索树（简单）
中序遍历，每遍历到一个节点，就把前驱结点的right指针指向当前节点。
就像插入链表节点一样，构造一个哨兵头节点和尾节点，将节点按中序遍历的顺序依次插入，由于递归函数要用到尾节点，所以将尾节点设置成类的成员变量。
重复的子问题——函数头设计
void dfs(TreeNode* root)
子问题在做什么——函数体设计
- dfs(root->left);
- tail->right = root; root->left = nullptr; tail = tail->right;
- dfs(root->right);
递归出口
当前节点是空节点，直接返回。
class Solution {
public:
TreeNode* increasingBST(TreeNode* root) {
TreeNode* preHead = new TreeNode;
tail = preHead;
dfs(root);
return preHead->right;
}
private:
void dfs(TreeNode* root)
{
if (root == nullptr)
return;
dfs(root->left);
tail->right = root;
root->left = nullptr;
tail = tail->right;
dfs(root->right);
}
TreeNode* tail;
};2. 验证二叉搜索树（中等）
定义一个类的成员变量，用来记录中序遍历过程中的前驱节点的值。那么就可以在中序遍历的过程中，先判断是否和前驱结点构成递增序列，如果递增，修改前驱结点的值为当前结点的值。
重复的子问题——函数头设计
bool isValidBST(TreeNode* root)
子问题在做什么——函数体设计
先递归判断左子树是否是二叉搜索树，如果不是，返回false（剪枝）；
然后判断当前节点的值是否>前驱节点的值，如果不是，返回false（剪枝），如果是，更新prev为当前节点的值；
然后递归判断右子树是否是二叉搜索树，如果不是，返回false（剪枝）；
我们已经把该剪的枝剪完了，最后返回true。
- 剪枝：if (isValidBST(root->left) == false) return false;
- 剪枝：if (root->val <= prev) return false;
- 更新：prev = root->val;
- 剪枝：if (isValidBST(root->right) == false) return false;
- return true;
递归出口
当前节点是空节点，返回true。
class Solution {
public:
bool isValidBST(TreeNode* root) {
if (root == nullptr)
return true;
// 判断左子树是否是二叉搜索树，如果不是二叉搜索树，则剪枝
if (isValidBST(root->left) == false)
return false;
// 判断当前节点的值是否>前驱节点的值，如果不是，则剪枝
if (root->val <= prev)
return false;
// 更新prev
prev = root->val;
// 判断右子树是否是二叉搜索树，如果不是二叉搜索树，则剪枝
if (isValidBST(root->right) == false)
return false;
return true;
}
private:
long long prev = LONG_LONG_MIN; // 测试用例卡边界值，初始值要比INT_MIN小
};3. 二叉搜索树中第K小的元素（中等）
我们只需要找到中序遍历序列的第k个节点即可。定义一个全局的计数器count，初始化为k，每扫描一个节点就count--，直到count==0时，扫描到第k个节点，记录答案ans（类的成员变量）。记录结果后，后续的遍历即失去意义，应提前返回。
重复的子问题——函数头设计
给一个节点，让当前节点的子树进行中序遍历。
void dfs(TreeNode* root)
子问题在做什么——函数体设计
先对左子树进行中序遍历，再扫描当前节点，执行count--，再判断count是否为0，==0则记录ans然后直接返回，!=0则继续对右子树进行中序遍历。
- dfs(root->left);
- if (--count == 0) {ans = root->val; return;}
- dfs(root->right);
递归出口
当前节点是空节点，直接返回。
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
count = k;
dfs(root);
return ans;
}
private:
void dfs(TreeNode* root)
{
if (root == nullptr)
return;
dfs(root->left);
if (--count == 0)
{
ans = root->val;
return;
}
dfs(root->right);
}
int count;
int ans;
};4. 把二叉搜索树转换为累加树（中等）
反序中序遍历：按照节点值从大到小遍历，先遍历右子树，再操作根节点，再遍历左子树。
该问题需要一个类的成员变量int sum记录所有比当前节点值大的节点值之和。
重复的子问题——函数头设计
TreeNode* convertBST(TreeNode* root)
子问题在做什么——函数体设计
- convertBST(root->right);
- sum += root->val; root->val = sum;
- convertBST(root->left);
- return root;
递归出口
当前节点是空节点，返回nullptr。
class Solution {
public:
TreeNode* convertBST(TreeNode* root) {
if (root == nullptr)
return nullptr;
convertBST(root->right);
sum += root->val;
root->val = sum;
convertBST(root->left);
return root;
}
private:
int sum = 0;
};后序遍历：
先递归处理左右子树，再处理当前节点，就是后序遍历。
1. 计算布尔二叉树的值（简单）
重复的子问题——函数头设计
bool evaluateTree(TreeNode* root)
子问题在做什么——函数体设计
递归求得左右子树的布尔值，然后将该节点的运算符对两个子树的值进行运算。
- bool left = evaluateTree(root->left); bool right = evaluateTree(root->right);
- 非叶子节点值为2表示逻辑或：return left || right;
非叶子节点值为3表示逻辑与：return left && right;
递归出口
当前节点是叶子节点时，直接返回其布尔值。
class Solution {
public:
bool evaluateTree(TreeNode* root) {
if (root->left == nullptr)
return root->val;
bool left = evaluateTree(root->left);
bool right = evaluateTree(root->right);
return root->val == 2 ? left || right : left && right;
}
};2. 二叉树剪枝（中等）
重复的子问题——函数头设计
TreeNode* pruneTree(TreeNode* root)
子问题在做什么——函数体设计
递归处理左右子树，并将新左右子树重新链接到当前节点；
如果当前节点是值为0的叶子节点，将其移除；
如果不是，返回当前节点。
- root->left = pruneTree(root->left);
- root->right = pruneTree(root->right);
- if (root->left == nullptr && root->right == nullptr && root->val == 0) return nullptr;
- return root;
递归出口
当前节点是空节点，返回nullptr。
class Solution {
public:
TreeNode* pruneTree(TreeNode* root) {
if (root == nullptr)
return nullptr;
root->left = pruneTree(root->left);
root->right = pruneTree(root->right);
if (root->left == nullptr && root->right == nullptr && root->val == 0)
{
// delete root; //面试题如果节点是new出来的，需要delete，防止内存泄露，笔试题可以不写
return nullptr;
}
return root;
}
};3. 二叉树中的最大路径和（困难）
创建一个类的成员变量ans，记录左子树->根节点->右子树的最大路径和。如果左子树贡献的最大路径和< 0，说明没有必要把左子树中的路径加入进去，认为左子树的贡献值为0即可，右子树也同理。
重复的子问题——函数头设计
函数返回值是从当前节点前往左子树或右子树的路径和的最大值
int dfs(TreeNode* root)
子问题在做什么——函数体设计
- 递归左右子树，分别计算出它们的最大贡献值，如果< 0，则认为是0：
int leftVal = max(dfs(root->left), 0); int rightVal = max(dfs(root->right), 0); - 计算左子树->当前节点->右子树的最大路径和：
int rootVal = leftVal + rightVal + root->val; - 更新ans：ans = max(ans, rootVal);
- 返回从当前节点前往左子树或右子树的路径和的最大值：
return root->val + max(leftVal, rightVal);
递归出口
当前节点是空节点，直接返回0。
class Solution {
public:
int maxPathSum(TreeNode* root) {
dfs(root);
return ans;
}
private:
int dfs(TreeNode* root)
{
if (root == nullptr)
return 0;
// 递归左右子树，分别计算出它们的最大贡献值
int leftVal = max(dfs(root->left), 0);
int rightVal = max(dfs(root->right), 0);
// 左子树->当前节点->右子树的最大路径和
int rootVal = leftVal + rightVal + root->val;
// 更新ans
ans = max(ans, rootVal);
return root->val + max(leftVal, rightVal);
}
int ans = INT_MIN;
};