【二叉树】（三）二叉树的基础修改构造及属性求解2

二叉树的所有路径

力扣原题链接：257. 二叉树的所有路径

给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

思路

• 这道题目要求从根节点到叶子的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径。
• 在这道题目中将第一次涉及到回溯，因为我们要把路径记录下来，需要回溯来回退一个路径再进入另一个路径。

前序遍历以及回溯的过程如图：

由于回溯算法将在下个章节重点学习，这里先提前了解一下即可，核心还在于前序的递归遍历的设计。

递归法

1. 递归函数参数以及返回值
要传入根节点，记录每一条路径的path，和存放结果集的result，这里递归不需要返回值，代码如下：

void traversal(TreeNode* node, vector<int>&path, vector<string>& res)

2. 确定递归终止条件
在写递归的时候都习惯了这么写：

if (cur == NULL) {终止处理逻辑
}

但是本题的终止条件这样写会很麻烦，因为本题要找到叶子节点，就开始结束的处理逻辑了（把路径放进result里）。

那什么时候算是找到叶子节点？ 是当 cur不为空，其左右孩子都为空的时候，就找到叶子节点。

所以本题的终止条件是：

//访问到子节点
if(node->left == NULL && node->right == NULL)
{//终止处理逻辑//把path内的数据封装成string格式，并添加至res
}

这里我们先使用vector结构的path容器来记录路径，那么终止处理逻辑如下：

//访问到子节点
if(node->left == NULL && node->right == NULL)
{string buf;for(int i = 0; i < path.size()-1; i++){buf += to_string(path[i]);buf += "->";}buf += to_string(path[path.size() - 1]);res.push_back(buf);return;
}

3. 确定单层递归逻辑
因为是前序遍历，需要先处理中间节点，中间节点就是我们要记录路径上的节点，先放进path中。

//中 先把叶子节点的值放入path
path.push_back(node->val);

回溯和递归是一一对应的，有一个递归，就要有一个回溯。所以回溯要和递归永远在一起，世界上最遥远的距离是你在花括号里，而我在花括号外！

//左
if(node->left)
{traversal(node->left, path, res);path.pop_back();	//回溯
}//右
if(node->right)
{traversal(node->right, path, res);path.pop_back();	//回溯
}

那么本题整体代码如下：

class Solution {
public:void traversal(TreeNode* node, vector<int>&path, vector<string>& res){//中 先把叶子节点的值放入pathpath.push_back(node->val);//访问到子节点if(node->left == NULL && node->right == NULL){string buf;for(int i = 0; i < path.size()-1; i++){buf += to_string(path[i]);buf += "->";}buf += to_string(path[path.size() - 1]);res.push_back(buf);return;}//左if(node->left){traversal(node->left, path, res);path.pop_back();	//回溯}//右if(node->right){traversal(node->right, path, res);path.pop_back();	//回溯}}vector<string> binaryTreePaths(TreeNode* root) {vector<int> path;vector<string> res;if(root == NULL)return res;traversal(root,path,res);return res;}
};

迭代法

至于非递归的方式，我们可以依然可以使用前序遍历的迭代方式来模拟遍历路径的过程，这里除了模拟递归需要一个栈，同时还需要一个栈来存放对应的遍历路径。

---

左叶子之和

力扣原题链接：404. 左叶子之和

计算给定二叉树的所有左叶子之和。

示例：

左叶子的明确定义：节点A的左孩子不为空，且左孩子的左右孩子都为空（说明是叶子节点），那么A节点的左孩子为左叶子节点

那么判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子。

如果该节点的左节点不为空，该节点的左节点的左节点为空，该节点的左节点的右节点为空，则找到了一个左叶子，判断代码如下：

if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) {左叶子节点处理逻辑
}

递归法

1. 确定递归函数的参数和返回值
判断一个树的左叶子节点之和，那么一定要传入树的根节点，递归函数的返回值为数值之和，所以为int。

int traversal(TreeNode* node)

2. 确定终止条件

• 如果遍历到空节点，那么左叶子值一定是0

  if(node == NULL)			//根节点为空 返回return 0;
  

• 注意，只有当前遍历的节点是父节点，才能判断其子节点是不是左叶子。 所以如果当前遍历的节点是叶子节点，那其左叶子也必定是0，那么终止条件为：

  if(node == NULL)			//根节点为空 返回return 0;
  if(node->left == NULL && node->right == NULL)	//叶子节点return 0;
  

3. 确定单层递归的逻辑
当遇到左叶子节点的时候，记录数值，然后通过递归求取左子树左叶子之和，和 右子树左叶子之和，相加便是整个树的左叶子之和

//递归遍历 左子树
int leftSum  = sumOfLeftLeaves(node->left);		
//存在左叶子
if(node->left && node->left->left == NULL && node->left->right == NULL)leftSum = node->left->val;//递归遍历 右子树
int rightSum = sumOfLeftLeaves(node->right);return leftSum + rightSum;		//中

整体递归代码如下：

class Solution {
public:int traversal(TreeNode* node){int sum = 0;if(node == NULL)			//根节点为空 返回return 0;if(node->left == NULL && node->right == NULL)	//叶子节点return 0;//递归遍历 左子树int leftSum  = sumOfLeftLeaves(node->left);		//存在左叶子if(node->left && node->left->left == NULL && node->left->right == NULL)leftSum = node->left->val;//递归遍历 右子树int rightSum = sumOfLeftLeaves(node->right);return leftSum + rightSum;						//中}int sumOfLeftLeaves(TreeNode* root) {int sum = traversal(root);return sum; }
};

迭代法

---

找树左下角的值

力扣原题链接：513. 找树左下角的值

本题要找出树的最后一行的最左边的值，显然此题用迭代法层序遍历最适合不过，其实用迭代法比递归法更简单一点点，至于迭代法比较简单，记录每层最左边一个元素后，最后返回即可，因此这里还是用递归法进行详细展开，迭代法只记录最后的实现代码

递归法

• 如果使用递归法，判断是最后一行其实就是深度最大的叶子节点一定是最后一行。
• 如何找最左边的呢？可以使用前序遍历（当然中序，后序都可以，因为本题没有 中间节点的处理逻辑，只要左优先就行），保证优先左边搜索，然后记录深度最大的叶子节点，此时就是树的最后一行最左边的值。

递归三部曲：

1. 确定递归函数的参数和返回值

• 参数必须有要遍历的树的根节点，还有就是一个int型的变量用来记录最长深度。 这里就不需要返回值了，所以递归函数的返回类型为void。
• 本题还需要类里的两个全局变量，maxDepth用来记录最大深度，res记录最大深度最左节点的数值。

  //递归函数
  void traversal(TreeNode* node, int depth)
  

2. 确定终止条件
当遇到叶子节点的时候，就需要统计一下最大的深度了，所以需要遇到叶子节点来更新最大深度，代码如下：

//找到叶子节点
if(node->left == NULL && node->right == NULL)
{if(depth > maxDepth){maxDepth = depth;res = node->val;}	
}

3. 确定单层递归的逻辑
在找最大深度的时候，递归的过程中依然要使用回溯，代码如下：

if(node->left)		//左
{depth++;		//加入左节点 深度+1traversal(node->left, depth);depth--;		//回溯
}if(node->right)		//右
{depth++;		//加入右节点 深度+1traversal(node->right, depth);depth--;		//回溯
}

完整代码如下：

class Solution {
public://递归法int maxDepth = -1;int res;//递归函数void traversal(TreeNode* node, int depth){//找到叶子节点if(node->left == NULL && node->right == NULL){if(depth > maxDepth){maxDepth = depth;res = node->val;}	}//中 不需要处理if(node->left)		//左{depth++;		//加入左节点 深度+1traversal(node->left, depth);depth--;		//回溯}if(node->right)		//右{depth++;		//加入右节点 深度+1traversal(node->right, depth);depth--;		//回溯}}int findBottomLeftValue(TreeNode* root) {traversal(root,0);return res;}
}

迭代法

迭代法的核心即覆盖记录每层最左边元素的值，最后返回记录的值即可。

class Solution {
public://层序遍历int findBottomLeftValue(TreeNode* root) {if(root == NULL)return 0;int size;queue<TreeNode*> que;int ret;			//记录每层最左边的节点值que.push(root);while(!que.empty()){//获取每层的节点个数size = que.size();ret =  que.front()->val;while(size--){TreeNode* node = que.front();que.pop();if(node->left)que.push(node->left);if(node->right)que.push(node->right);}size = que.size();	//跟新}return ret;}
};

---

路径总和

力扣原题链接：112. 路径总和

  给定二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

 
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true

 
1. 确定递归函数的参数和返回类型
参数： 需要二叉树的根节点，还需要一个计数器，这个计数器用来计算二叉树的一条边之和是否正好是目标和，计数器为int型。
返回值： 本题是找一条符合条件的路径，所以递归函数需要返回值，从下图可以看出，遍历的路线，并不要遍历整棵树，所以递归函数需要返回值，可以用bool类型表示。

 
所以代码如下：

bool traversal(TreeNode* node, int count)

2. 确定终止条件

• 不要去累加然后判断是否等于目标和，那么代码比较麻烦，可以用递减，让计数器count初始为目标和，然后每次减去遍历路径节点上的数值。
• 如果最后count == 0，同时到了叶子节点的话，说明找到了目标和。
• 如果遍历到了叶子节点，count不为0，就是没找到。

递归终止条件代码如下：

//遇到可行路径的叶子节点
if(node->left == NULL && node->right == NULL && count == 0)return true;		//一路减下来 是目标路径
//其他叶子节点
if(node->left == NULL && node->right == NULL)return false;

3. 确定单层递归的逻辑

• 因为终止条件是判断叶子节点，所以递归的过程中就不要让空节点进入递归了。
• 递归函数是有返回值的，如果递归函数返回true，说明找到了合适的路径，应该立刻返回。

代码如下：

//向左遍历
if(node->left)
{count -= node->left->val;bool ret = traversal(node->left,count);if(ret)						//如果存在 一路返回return true;count += node->left->val;	//回溯count 
}
//向右遍历
if(node->right)
{count -= node->right->val;bool ret = traversal(node->right,count);if(ret)						//如果存在 一路返回return true;count += node->right->val;	//回溯count 
}
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)return false;//向左遍历if(node->left){count -= node->left->val;bool ret = traversal(node->left,count);if(ret)						//如果存在 一路返回return true;count += node->left->val;	//回溯count }//向右遍历if(node->right){count -= node->right->val;bool ret = traversal(node->right,count);if(ret)						//如果存在 一路返回return true;count += node->right->val;	//回溯count }return false;}bool hasPathSum(TreeNode* root, int targetSum) {if(root == NULL)return false;int res = traversal(root, targetSum - root->val);return res;}
};

---

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

力扣原题链接：106. 从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

输入：

• 中序遍历：inorder = [9,3,15,20,7]
• 后序遍历：postorder = [9,15,7,20,3]，返回如下二叉树：

思路

  以 后序数组的最后一个元素为切割点，先切中序数组，根据中序数组，反过来再切后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。

流程如图：

那么代码应该怎么写呢？

说到一层一层切割，就应该想到了递归。

来看一下一共分几步：

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

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

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

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

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

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

根据思路写出每一步的代码，完整代码如下，但要注意以下几个点：

• 切割标准的定义：这里使用的是左闭右开
• 切割点在后序数组的最后一个元素，就是用这个元素来切割中序数组的，所以必要先切割中序数组
• 切割后续数组时，有一个很重的点，就是中序数组大小一定是和后序数组的大小相同的，后序数组就可以按照左中序数组的大小来切割，切成左后序数组和右后序数组。
• 代码写出来一定是各种问题，所以一定要加日志来调试，看看是不是按照自己思路来切割的，不要大脑模拟，那样越想越糊涂。

class Solution {
public:TreeNode* traversal(vector<int>& inorder, vector<int>& postorder){//1. 后续数组为空 返回if(postorder.empty())return NULL;//2. 获取根节点的值(后续数组中的最后一个值)int val = postorder[postorder.size() - 1];TreeNode* root = new TreeNode(val);if(postorder.size() == 1)		//只有1个叶子节点return root;//3. 找切割点 计算根节点的值在中序数组中的下标 int idx;		//根节点值在中序数组中的下标for(idx = 0; idx < postorder.size(); idx++){if(inorder[idx] == val)break;			}//要确定顺序得看后序，因为中序不知道中间节点在哪//4. 切割中序数组vector<int> inleft;		//左中序	[0,idx)vector<int> inright;	//右中序	[idx+1,size)for(int i = 0; i < idx; i++)		inleft.push_back(inorder[i]);	for(int i = idx+1; i < inorder.size(); i++)	inright.push_back(inorder[i]);//5. 切割后续数组vector<int> postleft;		//左后序	[0,size)vector<int> postright;		//右后序	[inleft.size, size)for(int i = 0; i < inleft.size(); i++)	postleft.push_back(postorder[i]);//左侧数组长度是一样的for(int i = inleft.size(); i < postorder.size() - 1; i++)	postright.push_back(postorder[i]);/*cout << "------------debug------------------" << endl;cout << "------------inorder------------------"<< endl;for(int i = 0; i < inorder.size();i++)cout << inorder[i] << " ";cout << endl;cout << "------------postorder------------------"<< endl;for(int i = 0; i < postorder.size();i++)cout << postorder[i] << " ";cout << endl;cout << "val = " << val << endl;cout << "idx = " << idx << endl;cout << "------------inleft------------------"<< endl;for(int i = 0; i < inleft.size();i++)cout << inleft[i] << " ";cout << endl;cout << "------------inright------------------"<< endl;for(int i = 0; i < inright.size();i++)cout << inright[i] << " ";cout << endl;cout << "------------postleft------------------"<< endl;for(int i = 0; i < postleft.size();i++)cout << postleft[i] << " ";cout << endl;cout << "------------postright------------------"<< endl;for(int i = 0; i < postright.size();i++)cout << postright[i] << " ";cout << endl;
*/	//6. 递归处理左区间、右区间root->left = traversal(inleft,postleft);root->right = traversal(inright,postright);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if(inorder.size() == 0 || postorder.size() == 0)return NULL;return traversal(inorder, postorder);}
};

---

最大二叉树

力扣原题链接：654. 最大二叉树

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

• 创建一个根节点，其值为 nums 中的最大值。

• 递归地在最大值 左边 的 子数组前缀上 构建左子树。

• 递归地在最大值 右边 的 子数组后缀上 构建右子树。

如果对于上一题有较好的理解与设计的话，那么本题相对比较简单，本题思路与上一题完全相似，且更简单。

思路

最大二叉树的构建过程如下：

1. 确定递归函数的参数和返回值

参数传入的是存放元素的数组，返回该数组构造的二叉树的头结点，返回类型是指向节点的指针。

代码如下：

TreeNode* traversal(vector<int>& nums) 

2. 确定终止条件

那么当递归遍历的时候，如果传入的数组大小为1，说明遍历到了叶子节点了。

那么应该定义一个新的节点，并把这个数组的数值赋给新的节点，然后返回这个节点。 这表示一个数组大小是1的时候，构造了一个新的节点，并返回。

代码如下：

TreeNode* node = new TreeNode(0);
if (nums.size() == 1) {node->val = nums[0];return node;
}

3. 确定单层递归的逻辑

这里有四步工作

• 先要找到数组中最大的值和对应的下标， 最大的值构造根节点，下标用来下一步分割数组。

  int maxValue = *max_element(nums.begin(),nums.end());
  int maxPosition = max_element(nums.begin(),nums.end()) - nums.begin();
  

• 最大值所在的下标左区间 构造左子树

  vector<int> leftNums;		//[0,pos)
  for(int i = 0; i < maxPosition; i++)leftNums.push_back(nums[i]);
  

• 最大值所在的下标右区间 构造右子树

  vector<int> rightNums;		//[Pos+1,size)
  for(int i = maxPosition + 1; i < nums.size(); i++)rightNums.push_back(nums[i]);
  

• 递归处理左右数组

  //4. 递归处理左右区间
  root->left  = traversal(leftNums);
  root->right = traversal(rightNums);return root;
  

完整版本代码：

class Solution {
public://做完106 再独立做这题 显得轻而易举 对比学习TreeNode* traversal(vector<int>& nums) {//1. 数组为空 返回if(nums.size() == 0)return NULL;//2. 获取最大值与最大值的下标int maxValue = *max_element(nums.begin(),nums.end());int maxPosition = max_element(nums.begin(),nums.end()) - nums.begin();TreeNode* root = new TreeNode(maxValue);//如果只有一个节点if(nums.size() == 1)return root;//3. 分割数组 形成左数组与右数组vector<int> leftNums;		//[0,pos)vector<int> rightNums;		//[Pos+1,size)for(int i = 0; i < maxPosition; i++)leftNums.push_back(nums[i]);for(int i = maxPosition + 1; i < nums.size(); i++)rightNums.push_back(nums[i]);//4. 递归处理左右区间root->left  = traversal(leftNums);root->right = traversal(rightNums);return root;}TreeNode* constructMaximumBinaryTree(vector<int>& nums) {if(nums.size() == 0)return NULL;return traversal(nums);}
};

合并二叉树

力扣原题链接：617. 合并二叉树

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

示例1：

 
示例2：

思路

• 其实和遍历一个树逻辑是一样的，只不过传入两个树的节点，同时操作。
• 本题使用哪种遍历都是可以的！

我们下面以前序遍历为例。

动画如下：

那么我们来按照递归三部曲来解决：

1. 确定递归函数的参数和返回值：
首先要合入两个二叉树，那么参数至少是要传入两个二叉树的根节点，返回值就是合并之后二叉树的根节点，代码如下：

TreeNode* traversal(TreeNode* root1, TreeNode* root2)

2. 确定终止条件：
因为是传入了两个树，那么就有两个树遍历的节点t1 和 t2，如果t1 == NULL 了，两个树合并就应该是 t2 了

//终止条件
if(root1 == NULL)return root2;
if(root2 == NULL)return root1;

3. 确定单层递归的逻辑：
这里重复利用一下t1这个树，t1就是合并之后树的根节点（就是修改了原来树的结构）。

• 那么单层递归中，就要把两棵树的元素加到一起。

• 接下来t1 的左子树是：合并 t1左子树 t2左子树之后的左子树。

• t1 的右子树：是合并 t1右子树 t2右子树之后的右子树。

最终t1就是合并之后的根节点，代码如下：

root1->val += root2->val;								//中
root1->left  = traversal(root1->left, root2->left);		//左
root1->right = traversal(root1->right, root2->right);	//右return root1;

完整代码如下：

class Solution {
public:TreeNode* traversal(TreeNode* root1, TreeNode* root2){//终止条件if(root1 == NULL)return root2;if(root2 == NULL)return root1;root1->val += root2->val;								//中root1->left  = traversal(root1->left, root2->left);		//左root1->right = traversal(root1->right, root2->right);	//右return root1;}TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {return traversal(root1, root2);}
};