【算法】二叉树中的 DFS
【ps】本篇有 6 道 leetcode OJ。
目录
一、算法简介
二、相关例题
1）计算布尔二叉树的值
.1- 题目解析
.2- 代码编写
2）求根节点到叶节点数字之和
.1- 题目解析
.2- 代码编写
3）二叉树剪枝
.1- 题目解析
.2- 代码编写
4）验证二叉搜索树
.1- 题目解析
.2- 代码编写
5）二叉搜索树中第K小的元素
.1- 题目解析
.2- 代码编写
6）二叉树的所有路径
.1- 题目解析
.2- 代码编写
一、算法简介
二叉树是一种经典的树结构，是节点的一个有限集合（该集合为空，或由一个根节点加上两棵别称为左子树和右子树的二叉树组成）。
二叉树中又有一些特别的类型，例如二叉搜索树、红黑树等。其中，二叉搜索树又称二叉排序树，是一种 key 搜索模型它或是一棵空树，亦或是具有以下性质的二叉树:
- 若根的左子树不为空，则左子树上所有节点的值都小于根节点的值；
- 若根的右子树不为空，则右子树上所有节点的值都大于根节点的值；
- 根的左右子树也分别为二叉搜索树。
二叉树中最常见的操作就是遍历整棵树，例如：
- 前序遍历：根->左子树->右子树。
- 中序遍历：左子树->根->右子树。
- 后序遍历：左子树->右子树->根。
- 层序遍历：根->下一层叶子节点->下下一层叶子节点...（一般用 BFS 实现）
遍历整棵树的过程，一般通过 DFS 来实现，且二叉树的题型最能展现 DFS 的特性。
DFS（深度优先搜索）是树或图这样的数据结构中常⽤的⼀种遍历算法，主要通过递归来实现。这个算法会尽可能深地搜索树或图中的分⽀，直到⼀条路径上的所有节点都被遍历完毕，然后再回溯到上⼀层，继续找另⼀条路遍历。
在⼆叉树中，树的定义本⾝就是递归定义，因此采⽤ DFS 的⽅法去实现树的前序遍历、中序遍历、后序遍历，不仅容易理解⽽且代码很简洁。前中后序三种遍历的唯⼀区别就是访问根节点的时机不同，在做题的时候，选择⼀个适当的遍历顺序，对于算法的理解是⾮常有帮助的。
二、相关例题
1）计算布尔二叉树的值
2331. 计算布尔二叉树的值
.1- 题目解析
整体地来看一棵树的话，题目就是要求根据根的运算符来求左孩子和右孩子的运算结果，而要求得根的运算结果，就要先知道整棵左子树的结果和整棵右子树的结果，由此，这个运算的过程其实是一个后序遍历，那么，我们对整棵树通过 DFS 进行一次后序遍历即可。
.2- 代码编写
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool evaluateTree(TreeNode* root) {
if(root->left==nullptr)return root->val==0 ? false : true;
bool l=evaluateTree(root->left);
bool r=evaluateTree(root->right);
bool ret=false;
if(root->val==2)ret=l|r;
else ret=l&r;
return ret;
}
};2）求根节点到叶节点数字之和
129. 求根节点到叶节点数字之和
.1- 题目解析
与上道题不同的是，本题是前序遍历。
.2- 代码编写
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int sumNumbers(TreeNode* root) {
return dfs(root,0);
}
int dfs(TreeNode* root,int presum)
{
presum=presum*10+root->val;
if(root->left==nullptr && root->right==nullptr)return presum;
int ret=0;
if(root->left)ret+=dfs(root->left,presum);
if(root->right)ret+=dfs(root->right,presum);
return ret;
}
};3）二叉树剪枝
814. 二叉树剪枝
.1- 题目解析
要删除二叉树中值为 0 的叶子节点，就要先删除左子树中的，再删除右子树，最后如果左子树和右子树都被删除了且根也是 0，那就把根也删除。也就是说，这其实是一个后序遍历的过程，而要删除值为 0 的叶子节点，只需将该节点置为空即可。
.2- 代码编写
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
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)
{
root=nullptr;
}
return root;
}
};4）验证二叉搜索树
98. 验证二叉搜索树
.1- 题目解析
【Tips】二叉搜索树的中序遍历的结果，一定是一个升序序列。
一颗二叉树要是二叉搜索树，那么根节点的左子树得是二叉搜索树，右子树也得是二叉搜索树。那么，我们可以通过中序遍历，先验证左子树是否是二叉搜索树，再将左孩子与根进行比较，然后再验证右子树是否是二叉搜索树，如果都满足二叉搜索树的性质，即左孩子 < 根 < 右孩子，那么整棵树就是一棵二叉搜索树。
.2- 代码编写
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
long prev=LONG_MIN; //用全局变量存储上一个孩子节点的值
public:
bool isValidBST(TreeNode* root) {
if(root==nullptr)return true;
bool left=isValidBST(root->left);//验证左子树
if(!left)return false; //剪枝
bool cur=false;
if(root->val > prev)cur=true; //验证根与左孩子
if(!cur)return false; //剪枝
prev=root->val; //记录上一个孩子节点的值
bool right=isValidBST(root->right);//验证右子树
return left && right && cur;
}
};5）二叉搜索树中第K小的元素
230. 二叉搜索树中第K小的元素
.1- 题目解析
我们可以仿照上一道题，在中序遍历时用两个全局变量来分别记录已经遍历的次数和相应节点的值。
.2- 代码编写
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
int count;
int ret;
public:
int kthSmallest(TreeNode* root, int k) {
count=k;
dfs(root);
return ret;
}
void dfs(TreeNode* root)
{
if(root==nullptr || count==0)return; //剪枝
dfs(root->left);
count--;
if(count==0)ret=root->val;
dfs(root->right);
}
};6）二叉树的所有路径
257. 二叉树的所有路径
.1- 题目解析
路径以字符串形式存储，从根节点开始前序遍历，每次遍历时将当前节点的值加⼊到路径中，如果该节点为叶子节点，将路径存储到结果中。否则，将 "->" 加⼊到路径中并递归遍历该节点的左右子树。
.2- 代码编写
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
vector<string> ret;//存储路径
public:
vector<string> binaryTreePaths(TreeNode* root) {
dfs(root,"");
return ret;
}
void dfs(TreeNode* root,string path)//便于回溯时恢复现场
{
path+=to_string(root->val);
if(!root->left && !root->right) //遍历到叶子节点，就停止添加节点值并记录当前结果
{
ret.push_back(path);
return;
}
path+="->";
if(root->left)dfs(root->left,path);
if(root->right)dfs(root->right,path);
}
};