前言
今日文案：
哀愁的人，给他们安慰，饥饿的人，给他们食物，而我所能做的，为什么总只是后者。
——三毛《温柔的夜》
一、找树左下角的值
class Solution { public: int maxdepth=-1; int res=0; void traversal(TreeNode*root,int depth) { if(root->left==NULL&&root->right==NULL) //叶子节点是返回条件 { if(depth>maxdepth) //找出深度最大的，保持值就行 { maxdepth=depth; res=root->val; } return ; } if(root->left) //遍历所有节点，优先左节点 { depth++; traversal(root->left,depth); depth--; //回溯 } if(root->right) { depth++; traversal(root->right,depth); depth--; } } int findBottomLeftValue(TreeNode* root) { traversal(root,0); return res; } };
二、路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
解题思路：
关键是使用回溯，在遍历所有数组的时候，记得要设置回溯。
class Solution { public: int sum=0; bool traversal(TreeNode*root,int tarfetSum) { if(root->right==0&&root->left==0) 叶子节点 { if(sum==tarfetSum) //判断 return true; else return false; } if(root->left) { sum+=root->left->val; if(traversal(root->left,tarfetSum)) { return true; } sum-=root->left->val; //回溯 } if(root->right) { sum+=root->right->val; if(traversal(root->right,tarfetSum)) { return true; } sum-=root->right->val; } return false; } bool hasPathSum(TreeNode* root, int targetSum) { if(root==0) return false; else sum+=root->val; return traversal(root,targetSum); } };
三、路径总和||
解题思路：
和层序遍历差不多，主要是回溯的问题。
class Solution { public: int sum=0; vector<int> path; vector<vector<int>> ans; void traversal(TreeNode*root,int targetSum) { if(root->left==NULL&&root->right==NULL) { if(sum==targetSum) //判断条件 { ans.push_back(path); //储存 return; } else return; } if(root->left) { path.push_back(root->left->val); sum+=root->left->val; traversal(root->left,targetSum); path.pop_back(); //回溯 sum-=root->left->val; //回溯 } if(root->right) { path.push_back(root->right->val); sum+=root->right->val; traversal(root->right,targetSum); path.pop_back(); sum-=root->right->val; } } vector<vector<int>> pathSum(TreeNode* root, int targetSum) { if(root==0) return ans; else { path.push_back(root->val); sum+=root->val; traversal(root,targetSum); } return ans; } };
四、从中序与后序遍历序列构造二叉树
解题思路：
本题的核心在于切割数组，中序和后序的顺序是，左中右，左右中，那么我们可以很简单地从后序数组中找出我们的中节点，我们取它的值去遍历中序数组，找到中节点，中节点左边就是左子树，右边就是右子树，这样我们又可以折射回后序数组，如此反复，完成构建，具体代码以及解析如下。
class Solution { public: TreeNode*traversal(vector<int>& inorder, vector<int>& postorder) { if(postorder.size()==0) //如果后序数组为0，那就等于没有中节点了，返空吧 { return NULL; } int rootVal=postorder[postorder.size()-1]; //记录后序数组最后一个值 int i=0; //后面要记录下标 for(i=0;i<inorder.size();i++) //遍历 { if(rootVal==inorder[i]) { break; //找到了直接出 } } TreeNode*root=new TreeNode(rootVal); //创建新节点 if (postorder.size() == 1) return root; postorder.resize(postorder.size()-1); //后序数组去掉末尾 vector<int> leftinorder(inorder.begin(),inorder.begin()+i); //中序左子树 vector<int> rightinorder(inorder.begin()+i+1,inorder.end()); //中序右子树 //记得此处加1，因为是左开右闭且跳过中 vector<int> leftpostorder(postorder.begin(),postorder.begin()+leftinorder.size()); //后序左子树 vector<int> righpostorde(postorder.begin()+leftinorder.size(),postorder.end()); root->left=traversal(leftinorder,leftpostorder); root->right=traversal(rightinorder,righpostorde); return root; } TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { return traversal( inorder, postorder); } };
总结
分清楚前中后序的处理逻辑
