第六章 二叉树 part05

1.LeetCode.找树左下角的值

1.1题目链接：513.找树左下角的值

文章讲解：代码随想录
视频讲解：B站卡哥视频

1.2思路：本题要找出树的最后一行的最左边的值。此时大家应该想起用层序遍历是非常简单的了，反而用递归的话会比较难一点；如果使用递归法，如何判断是最后一行呢，其实就是深度最大的叶子节点一定是最后一行；那么如何找最左边的呢？可以使用前序遍历（当然中序，后序都可以，因为本题没有 中间节点的处理逻辑，只要左优先就行），保证优先左边搜索，然后记录深度最大的叶子节点，此时就是树的最后一行最左边的值。

1.3附加代码如下所示：

（1）递归法

//递归法 
class Solution {
public:int maxdepth=INT_MIN;int result;void traversal(TreeNode*node,int depth){//终止条件if(node->left==NULL&&node->right==NULL)//当遇到叶子节点的时候，就需要统计一下最大的深度了，所以需要遇到叶子节点来更新最大深度{if(depth>maxdepth){maxdepth=depth;result=node->val;}return;}if(node->left)//左{depth++;traversal(node->left,depth);depth--;//回溯}if(node->right)//右{depth++;traversal(node->right,depth);depth--;}return;}int findBottomLeftValue(TreeNode* root) {traversal(root,1);return result;}
};

（2）迭代法

//迭代法 层序遍历
class Solution {
public:int findBottomLeftValue(TreeNode* root) {queue<TreeNode*>que;if(root!=NULL)que.push(root);int result=0;while(!que.empty()){int size=que.size();for(int i=0;i<size;i++){TreeNode*node=que.front();que.pop();if(i==0)result=node->val;//一直遍历到最后一行的第一个节点就是二叉树的左下角的值if(node->left)que.push(node->left);if(node->right)que.push(node->right);}}return result;}
};

2.LeetCode. 路径总和

2.1题目链接：112. 路径总和

文章讲解：代码随想录
视频讲解：B站卡哥视频

2.2思路：可以使用深度优先遍历的方式（本题前中后序都可以，无所谓，因为中节点也没有处理逻辑）来遍历二叉树，

再来看返回值，递归函数什么时候需要返回值？什么时候不需要返回值？这里总结如下三点：

如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。（这种情况就是本文下半部分介绍的113.路径总和ii）

如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。 （这种情况我们在236. 二叉树的最近公共祖先 (opens new window)中介绍）

如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。（本题的情况）

确定递归函数的参数和返回类型
参数：需要二叉树的根节点，还需要一个计数器，这个计数器用来计算二叉树的一条边之和是否正好是目标和，计数器为int型。
而本题我们要找一条符合条件的路径，所以递归函数需要返回值，及时返回，那么返回类型是什么呢？

如图所示：

2.3附加代码如下所示：

（1）路径总和

//迭代法
class Solution {
public:bool hasPathSum(TreeNode* root, int targetSum) {// 此时栈里要放的是pair<节点指针，路径数值>stack<pair<TreeNode*,int>>stk;//保存树的遍历节点,用pair<TreeNode*,int>及保存遍历的树节点又能吧遍历的路径数值之和存放起来if(root==NULL)return false;stk.push(pair<TreeNode*,int>(root,root->val));while(!stk.empty()){pair<TreeNode*,int> node=stk.top(); stk.pop();// 如果该节点是叶子节点了，同时该节点的路径数值等于sum，那么就返回trueif(node.first->left==NULL&&node.first->right==NULL&&targetSum==node.second){return true;}if(node.first->left)//左{stk.push(pair<TreeNode*,int>(node.first->left,node.second+node.first->left->val));}if(node.first->right)//右{stk.push(pair<TreeNode*,int>(node.first->right,node.second+node.first->right->val));}}return false;}
};

//递归法 
class Solution {
public:bool traversal(TreeNode*node,int count){//终止条件if(node->left==NULL&&node->right==NULL&&count==0){return true;}if(node->left==NULL&&node->right==NULL&&count!=0){return false;}if(node->left)//左{count-=node->left->val;if(traversal(node->left,count))return true;count+=node->left->val;}if(node->right)//右{count-=node->right->val;if(traversal(node->right,count))return true;count+=node->right->val;}return false;}bool hasPathSum(TreeNode* root, int targetSum) {if(root==NULL)return false;return traversal(root,targetSum-root->val);}
};

（2）路径总和Ⅱ

class Solution {
private:vector<vector<int>>result;vector<int>path;// 递归函数不需要返回值，因为我们要遍历整个树void traversal(TreeNode*node,int count){//终止条件if(node->left==NULL&&node->right==NULL&&count==0){result.push_back(path);return;}if(node->left==NULL&&node->right==NULL&&count!=0)return;if(node->left)//左{count-=node->left->val;path.push_back(node->left->val);traversal(node->left,count);count+=node->left->val;//计数值回溯path.pop_back();//路径节点值回溯}if(node->right)//右{count-=node->right->val;path.push_back(node->right->val);traversal(node->right,count);count+=node->right->val;//计数值回溯path.pop_back();//路径节点值回溯}}public:vector<vector<int>> pathSum(TreeNode* root, int targetSum) {result.clear();//如果Solution类的实例只被使用一次，那么这两行代码可以省略，因为result和path在每次创建Solution类的新实例时都会是空的。path.clear();//这两行代码是为了清楚之前调用该函数的执行结果if(root==NULL)return result;path.push_back(root->val);//把根节点放进去traversal(root,targetSum-root->val);return result;}
};

3.LeetCode.从中序与后序遍历序列构造二叉树

3.1题目链接：106.从中序与后序遍历序列构造二叉树

文章讲解：代码随想录
视频讲解：B站卡哥视频

3.2思路：以后序数组的最后一个元素为切割点，先切中序数组，根据中序数组，反过来再切后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。注意采用前序遍历和后序遍历是不能得到完整二叉树的（具体可以自己画图一目了然）。

整体思路步骤：
说到一层一层切割，就应该想到了递归。

来看一下一共分几步：

第一步：如果数组大小为零的话，说明是空节点了。

第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。

第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点

第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）

第五步：切割后序数组，切成后序左数组和后序右数组

第六步：递归处理左区间和右区间

3.3附加代码如下所示：

//递归法 
class Solution {
public:TreeNode*traversal(vector<int>& inorder, vector<int>& postorder){if(postorder.size()==0)return NULL;int rootvalue=postorder[postorder.size()-1];TreeNode*root=new TreeNode(rootvalue);//找到根节点int index;for(index=0;index<inorder.size();index++){if(inorder[index]==rootvalue)break;//找到中序数组切割点}//切割中序遍历数组为左中序和右中序vector<int>leftinorder(inorder.begin(),inorder.begin()+index);vector<int>rightinorder(inorder.begin()+index+1,inorder.end());postorder.resize(postorder.size()-1);//重新定义后续数组的大小，因为要把之前的根节点去掉//切割后序遍历数组为左后序和右后序vector<int>leftpostorder(postorder.begin(),postorder.begin()+leftinorder.size());vector<int>rightpostorder(postorder.begin()+leftinorder.size(),postorder.end());root->left=traversal(leftinorder,leftpostorder);//左子树root->right=traversal(rightinorder,rightpostorder);//右子树return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if(postorder.size()==0||inorder.size()==0)return NULL;return  traversal(inorder,postorder);}
};