目录
1.计算布尔二叉树的值1.题目链接2.算法原理详解3.代码实现
2.求根节点到叶节点数字之和1.题目链接2.算法原理详解3.代码实现
3.二叉树剪枝1.题目链接2.算法原理详解3.代码实现
4.验证二叉搜索树1.题目链接2.算法原理详解3.代码实现
5.二叉搜索树中第K小的元素1.题目链接2.算法原理详解3.代码实现
6.二叉树的所有路径1.题目链接2.算法原理详解3.代码实现
1.计算布尔二叉树的值
1.题目链接
计算布尔二叉树的值
2.算法原理详解
题目理解： 流程：
重复子问题 -> 函数头：
bool DFS(Node* root) 只关心某一个子问题在做什么 -> 函数体实现
bool left = DFS(root->leftbool right = DFS(root->right)根据当前结点进行响应运算 递归出口：叶子结点则返回
root->left == nullptr -> return root
3.代码实现
bool EvaluateTree(TreeNode* root)
{
// 函数出口
if(root->left == nullptr)
{
return root->val;
}
auto left = evaluateTree(root->left);
auto right = evaluateTree(root->right);
return root->val == 2 ? left | right : left & right;
}
2.求根节点到叶节点数字之和
1.题目链接
求根节点到叶节点数字之和
2.算法原理详解
思路：前序遍历的过程中，可以往左右⼦树传递信息，并且在回溯时得到左右⼦树的返回值
将⽗节点的数字与当前节点的信息整合到⼀起，计算出当前节点的数字，然后传递到下⼀层进⾏递归当遇到叶⼦节点的时候，就不再向下传递信息，⽽是将整合的结果向上⼀直回溯到根节点在递归结束时，根节点需要返回的值也就被更新为了整棵树的数字和 流程：
重复子问题 -> 函数头：int DFS(TreeNode* root, int prevNum)
返回值：当前子树计算的结果参数prevNum：父节点的数字 只关心某一个子过程在做什么-> 函数体
整合⽗节点的信息与当前节点的信息计算当前节点数字，并向下传递，在回溯时返回当前⼦树数字和 递归出口：叶子节点
3.代码实现
class Solution
{
public:
int sumNumbers(TreeNode* root)
{
return DFS(root, 0);
}
int DFS(TreeNode* root, int prevSum)
{
if(root == nullptr)
{
return 0;
}
prevSum = prevSum * 10 + root->val;
if(root->left == nullptr && root->right == nullptr)
{
return prevSum;
}
return DFS(root->left, prevSum) + DFS(root->right, prevSum);
}
};
3.二叉树剪枝
1.题目链接
二叉树剪枝
2.算法原理详解
通过决策树，抽象出递归的三个核心问题
函数头：Node* DFS(Node* root)函数体：
处理左子树处理右子树判断 递归出口：root == nullptr
3.代码实现
TreeNode* PruneTree(TreeNode* root)
{
if(root == nullptr)
{
return nullptr;
}
root->left = pruneTree(root->left);
root->right = pruneTree(root->right);
if(!root->val && !root->left && !root->right)
{
delete root; // 防止内存泄漏
root = nullptr;
}
return root;
}
4.验证二叉搜索树
1.题目链接
验证二叉搜索树
2.算法原理详解
通过此题可以感受出「全局变量的优势」「回溯」「剪枝」思路：如果⼀棵树是⼆叉搜索树，那么它的中序遍历的结果⼀定是⼀个严格递增的序列
可以初始化⼀个⽆穷⼩的全局变量，⽤来记录中序遍历过程中的前驱结点那么就可以在中序遍历的过程中，先判断是否和前驱结点构成递增序列，然后修改前驱结点为当前结点，传入下⼀层的递归中 方法一：依次执行以下判断
左子树是不是二叉搜索树当前节点是否复合二叉搜索树的定义右子树是不是二叉搜索树 方法二：法一 + 剪枝
3.代码实现
// v1.0 暴力判断
class Solution
{
long prev = LONG_MIN;
public:
bool isValidBST(TreeNode* root)
{
if(root == nullptr)
{
return true;
}
// 判断左子树
bool left = isValidBST(root->left);
// 判断自己
bool cur = false;
if(root->val > prev)
{
cur = true;
}
prev = root->val;
// 判断右子树
bool right = isValidBST(root->right);
return left && right && cur;
}
};
------------------------------------------------------------------------
// v2.0 剪枝
class Solution
{
long prev = LONG_MIN;
public:
bool isValidBST(TreeNode* root)
{
if(root == nullptr)
{
return true;
}
// 1.判断左子树
bool left = isValidBST(root->left);
if(!left) // 剪枝
{
return false;
}
// 2.判断自己
bool cur = false;
if(root->val > prev)
{
cur = true;
}
prev = root->val;
if(!cur) // 剪枝
{
return false;
}
// 3.判断右子树
bool right = isValidBST(root->right);
return left && right && cur;
}
};
5.二叉搜索树中第K小的元素
1.题目链接
二叉搜索树中第K小的元素
2.算法原理详解
通过此题可以感受出「全局变量的优势」「回溯」「剪枝」思路：
创建⼀个全局的计数器count，将其初始化为k，每遍历⼀个节点就将count--，直到某次递归的时候，count == 0，说明此时的结点就是要找的结果创建一个全局的ret，用于存储最终结果，简化返回值设计
3.代码实现
class Solution
{
int count, 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);
if(--count == 0)
{
ret = root->val;
}
DFS(root->right);
}
};
6.二叉树的所有路径
1.题目链接
二叉树的所有路径
2.算法原理详解
通过此题可以感受出「全局变量的优势」「回溯」「剪枝」
全局变量：保存结果回溯：恢复现场，通常有两种做法
全局变量函数传参(本题以它为主实现) 剪枝：加快搜索过程(本题可有可无) 流程：
函数头：void DFS(Node* root, string path)函数体：
if(root != nullptr)，就将当前节点的值加⼊路径path中，否则直接返回判断当前节点是否为叶⼦节点
如果是，则将当前路径加⼊到所有路径的存储数组ret中否则，将当前节点值加上"->"作为路径的分隔符，继续递归遍历当前节点的左右⼦节点 递归出口：if(root == nullptr) return;
3.代码实现
class Solution
{
vector
public:
vector
{
DFS(root, "");
return ret;
}
// 参数path实现回溯
void DFS(TreeNode* root, string path)
{
path += to_string(root->val);
// 叶子结点 + 函数出口
if(!root->left && !root->right)
{
ret.push_back(path);
}
path += "->";
// 非叶子结点 + 剪枝
if(root->left)
{
DFS(root->left, path);
}
if(root->right)
{
DFS(root->right, path);
}
}
};
参考链接
发表评论