文章目录
二叉树中的深搜有三种方法
-
前序遍历
根->左子树->右子树 -
中序遍历
左子树->根->右子树 -
前序遍历
左子树->右子树->根
计算布尔二叉树的值
题目：计算布尔二叉树的值
思路
- 如果当前节点
node为叶子节点，那么节点的值为它本身 - 如果当前节点
node含有孩子节点，对其孩子节点进行递归，计算出其左右孩子节点的值为； -
- 如果
node == 2，返回两孩子节点的|运算结果；如果node == 3，返回两孩子节点的&运算结果；
- 如果
因为是完全二叉树：每个节点有
0个或者2个孩子的二叉树。
所以对于递归出口，我们仅需判断当前节点的左孩子是否为空，如果为空，则当前节点为叶子节点；
C++代码
/**
* 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;
}
if (root->val == 2)
return evaluateTree(root->left) || evaluateTree(root->right);
else
return evaluateTree(root->left) && evaluateTree(root->right);
}
};
求根节点到叶节点数字之和
题目：求根节点到叶节点数字之和
思路
- 从根节点开始，遍历每个节点，如果遇到叶子节点，则将叶子节点对应的数字加到数字之和。如果当前节点不是叶子节点，则计算其子节点对应的数字，然后对子节点递归遍历。
C++代码
/**
* 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 dfs(TreeNode *root, int preSum)
{
preSum = preSum * 10 + root->val;
if(root->left == nullptr && root->right == nullptr)
return preSum;
int res = 0;
if(root->left) res += dfs(root->left, preSum);
if(root->right) res += dfs(root->right, preSum);
return res;
}
int sumNumbers(TreeNode* root)
{
return dfs(root, 0);
}
};
二叉树剪枝
题目：二叉树剪枝
思路
返回移除了所有不包含
1的子树的原二叉树。
意思即，删除所有子树没有1的节点
我们要根据其左右子树的状态来判断当前节点能否删除，所有我们使用后序遍历
C++代码
/**
* 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)
{
return nullptr;
}
root->left = pruneTree(root->left);
root->right = pruneTree(root->right);
if(!root->left && !root->right && root->val == 0)
{
delete root;
root = nullptr;
}
return root;
}
};
验证二叉搜索树
题目：验证二叉搜索树
思路
二叉搜索树：左子树小于根节点；右子树大于根节点
我们知道，二叉搜索树的中序遍历结果是一个有序的数组，所以我们会有这样一个想法：对其进行中序遍历，并将每一个结果的值保存在一个数组中，最后判断该数组是否有序；
使用一个全局变量存储上一个用于对比的数值
C++代码
/**
* 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) return true;
if(!isValidBST(root->left)) return false;
if (prev != LONG_MIN && (root->val <= prev))
return false;
prev = root->val;
return isValidBST(root->right);
}
};
二叉搜索树中第 K 小的元素
思路
两个全局变量 + 中序遍历
- 一个来标记，次数
count；- 一个来标记，结果
ret；
C++代码
/**
* 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, ret;
void dfs(TreeNode* root)
{
if(!root || !count) return ;
dfs(root->left);
if(!(--count)) ret = root->val;
dfs(root->right);
}
public:
int kthSmallest(TreeNode* root, int k)
{
count = k;
dfs(root);
return ret;
}
};
二叉树的所有路径
二叉树的所有路径
题目：二叉树的所有路径
思路
- 在
dfs函数中，首先将当前节点的值转换为字符串并添加到path中。 - 检查当前节点是否为叶子节点（即没有左子节点和右子节点）。如果是叶子节点，将
path添加到结果数组res中，并返回。 - 如果当前节点不是叶子节点，则继续递归搜索其左子节点和右子节点。
- 在递归调用
dfs时，对于非叶子节点，需要在path后添加->符号
C++代码
/**
* 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
{
void dfs(TreeNode* root, string path, vector<string>& res)
{
path += to_string(root->val);
if(root->left == nullptr && root->right == nullptr) // 叶子节点不添加 "->"
{
res.push_back(path);
return;
}
if(root->left) dfs(root->left, path + "->", res);
if(root->right) dfs(root->right, path + "->", res);
return;
}
public:
vector<string> binaryTreePaths(TreeNode* root)
{
vector<string> res;
string path;
dfs(root, path, res);
return res;
}
};