---

经典 700 二叉搜索树中的搜索

开塞递归

我并没有用到二叉搜索树这个前提
1、输入输出TreeNode* searchBST(TreeNode* root, int val)
2、退出：遍历到空或者满足输入的int则退出
if(root == nullptr || root->val == val) return root;
3、层级逻辑

TreeNode* temp;
temp = searchBST(root->left, val);
if(temp == nullptr){temp = searchBST(root->right, val); return temp;
}
return temp;

其中的if为如果没有在左子树上搜索得到能用的TreeNode再搜右子树

4、整合

TreeNode* searchBST(TreeNode* root, int val) {if(root == nullptr || root->val == val) return root;TreeNode* temp;temp = searchBST(root->left, val);if(temp == nullptr){temp = searchBST(root->right, val); return temp;}return temp;
}

迭代

充分利用二叉搜索树特性，左小于中、右大于中

TreeNode* searchBST(TreeNode* root, int val) {while (root != NULL) {if (root->val > val) root = root->left;else if (root->val < val) root = root->right;else return root;}return NULL;
}

1 404 左叶子之和

递归

在遍历二叉树的过程中，我们需要不断地向下递归，遍历左右子树，并在递归回溯的过程中累加所有左叶子的值。在递归遍历左子树后，我们需要回溯到当前节点，然后递归遍历右子树。这种递归回溯的过程与回溯算法类似，因此可以说，这段代码也是一种使用了回溯思想的算法实现。

整体思想：
如果当前节点的左子节点是叶子节点，那么就将它的值累加到leftLeafSum变量中。否则，递归遍历当前节点的左子树，将返回的值累加到leftLeafSum中。然后，递归遍历当前节点的右子树，将返回的值累加到leftLeafSum中，并最终返回累加结果。

递归三部曲：
1、递归函数输入输出
输入：节点；输出：累计和
int sumOfLeftLeaves(TreeNode* root)
2、退出条件：正常退出
if (root == nullptr) return 0;
3、底层逻辑
3.1 定义一个存储值int leftLeafSum
3.2 如果当前节点的左子节点是叶子节点：累加；如果不是则遍历

if (root->left != nullptr && root->left->left == nullptr && root->left->right == nullptr) {// 如果当前节点的左子节点是叶子节点，累加它的值leftLeafSum += root->left->val;} else {// 如果当前节点的左子节点不是叶子节点，递归遍历它的左子树leftLeafSum += sumOfLeftLeaves(root->left);
}

3.2 递归遍历当前节点的右子树
leftLeafSum += sumOfLeftLeaves(root->right);

4、整合

int sumOfLeftLeaves(TreeNode* root) {if (root == nullptr) return 0;int leftLeafSum = 0;if (root->left != nullptr && root->left->left == nullptr && root->left->right == nullptr) {// 如果当前节点的左子节点是叶子节点，累加它的值leftLeafSum += root->left->val;} else {// 如果当前节点的左子节点不是叶子节点，递归遍历它的左子树leftLeafSum += sumOfLeftLeaves(root->left);}// 递归遍历当前节点的右子树leftLeafSum += sumOfLeftLeaves(root->right);return leftLeafSum;
}

2 513 找树左下角的值

层序遍历

很简单，复习一下层序遍历

int findBottomLeftValue(TreeNode* root) {queue<TreeNode*> que;if(root != nullptr) que.push(root);int res = 0;while(!que.empty()){int size = que.size();for(int i = 0; i < size; ++i){TreeNode* temp = que.front();que.pop();if(temp->left != nullptr) que.push(temp->left);if(temp->right != nullptr) que.push(temp->right);if(i == 0){res = temp->val;}}}return res;}

递归

暂时不管

3 112 路径总和

递归回溯

遍历的路线不需要遍历整棵树，所以递归函数需要返回值，可以用bool类型表示。

1、输入输出
bool hasPathSum(TreeNode* root, int targetSum)
2、退出条件
两种情况，第二种为碰到叶子节点时，判断当前叶子节点的val是否等于输入的int

if (root == nullptr) return false;
if(root->left == nullptr && root->right == nullptr)  {return targetSum == root->val;
}

3、单层逻辑

// 递归遍历左右子树
int a = targetSum - root->val;   // 所谓的回溯在这里
bool ll = hasPathSum(root->left, a);
int b = targetSum - root->val;
bool rr = hasPathSum(root->right, b);
return ll || rr;

4、整合

bool hasPathSum(TreeNode* root, int targetSum) {if (root == nullptr) return false;if (root->left == nullptr && root->right == nullptr) {// 如果当前节点是叶子节点，判断当前路径的和是否等于目标和return targetSum == root->val;}// 递归遍历左右子树int a = targetSum - root->val;   // 所谓的回溯在这里bool ll = hasPathSum(root->left, a);int b = targetSum - root->val;bool rr = hasPathSum(root->right, b);return ll || rr;
}

迭代 stack（看看即可）

bool haspathsum(TreeNode* root, int sum) {if (root == null) return false;// 此时栈里要放的是pair<节点指针，路径数值>stack<pair<TreeNode*, int>> st;st.push(pair<TreeNode*, int>(root, root->val));while (!st.empty()) {pair<TreeNode*, int> node = st.top();st.pop();// 如果该节点是叶子节点了，同时该节点的路径数值等于sum，那么就返回trueif (!node.first->left && !node.first->right && sum == node.second) return true;// 右节点，压进去一个节点的时候，将该节点的路径数值也记录下来if (node.first->right) {st.push(pair<TreeNode*, int>(node.first->right, node.second + node.first->right->val));}// 左节点，压进去一个节点的时候，将该节点的路径数值也记录下来if (node.first->left) {st.push(pair<TreeNode*, int>(node.first->left, node.second + node.first->left->val));}}return false;
}

4 113 路径总和 II 此题需要前博客 二叉树（4）回溯 的基础

递归回溯

感觉三部曲也没啥用，靠感觉写

class Solution {
public:void trans(TreeNode* root, int targetSum, vector<int> path, vector<vector<int>>& res){// path.push_back(root->val);   // 不写这儿，不好理解if (root == nullptr) return;if(root->left == nullptr && root->right == nullptr)  // 如果这个是叶子节点{if(targetSum == root->val){// 说明这个叶子节点的上面那条路是待保存的pathres.push_back(path);}}// 递归遍历左右子树if(root->left != nullptr){int a = targetSum - root->val;path.push_back(root->left->val);trans(root->left, a, path, res);path.pop_back();   // 回溯}if(root->right != nullptr) {int b = targetSum - root->val;path.push_back(root->right->val);trans(root->right, b, path, res);path.pop_back();   // 回溯}return;}vector<vector<int>> pathSum(TreeNode* root, int targetSum) {vector<vector<int>> res;vector<int> path;if(root == nullptr) return res;else path.push_back(root->val);trans(root, targetSum, path, res);return res;}
};

5 617 合并二叉树

首道需要构造二叉树的题，同时遍历两颗树
1、输入输出 TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2)
2、退出条件
3、层逻辑
3.1 创建一个新的头结点，值为其余的两个头相加
TreeNode* newNode = new TreeNode(root1->val + root2->val);
3.2 新头->left为左遍历
newNode->left = mergeTrees(root1->left, root2->left);
3.3 新头->right为右遍历
newNode->right = mergeTrees(root1->right, root2->right);

4、整合

TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if (root1 == nullptr && root2 == nullptr) {return nullptr;}if (root1 == nullptr) {return root2;}if (root2 == nullptr) {return root1;}TreeNode* newNode = new TreeNode(root1->val + root2->val);newNode->left = mergeTrees(root1->left, root2->left);newNode->right = mergeTrees(root1->right, root2->right);return newNode;
}