二叉树中的深搜有三种方法

• 前序遍历
  根->左子树->右子树

• 中序遍历
  左子树->根->右子树

• 前序遍历
  左子树->右子树->根

计算布尔二叉树的值

题目：计算布尔二叉树的值

思路

• 如果当前节点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);elsereturn 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 小的元素

题目：二叉搜索树中第 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;}
};