二叉树构建与遍历-LeetCode 889、1008、129、113
二叉树构建与遍历-LeetCode 889、1008、129、113
编程题
【LeetCode #889】根据前序和后序遍历构建二叉树
返回与给定的前序和后序遍历匹配的任何二叉树。 pre 和 post 遍历中的值是不同的正整数。
示例： 输入：pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1] 输出：[1,2,3,4,5,6,7]
解题思路：
还是一样的套路，找出左右子树的数值范围，然后递归的构建！我们知道pre中第一个值为根节点的值，而post最后一个是根节点的值！并且这两个遍历的方式区别为： pre: 根节点 前序左节点 前序右节点 post: 后序左节点 后序有节点 根节点 因此，第一次构建左子树时，将根节点去除，则此时子树根节点为2，那么就可以由post得到该子树的长度，进而将pre和post拆分成两个序列！转化为构建左右子树的子问题！
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
if(pre.size() == 0 || post.size() == 0) return nullptr;
TreeNode* root = new TreeNode(pre[0]);
if(pre.size() == 1) return root; // 由于下面要使用pre[1]，因此必须判断其个数
auto it = find(post.begin(), post.end(), pre[1]);
int len = it - post.begin() + 1; // 左子树长度
vector<int> preleft(pre.begin()+1, pre.begin()+1+len); // 一样的套路，不在赘述
vector<int> preright(pre.begin()+1+len, pre.end());
vector<int> postleft(post.begin(), post.begin()+len);
vector<int> postright(post.begin()+len, post.end()-1);
root->left = constructFromPrePost(preleft, postleft);
root->right = constructFromPrePost(preright, postright);
return root;
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/
【LeetCode #1008】先序遍历构造二叉树
返回与给定先序遍历 preorder 相匹配的二叉搜索树（binary search tree）的根结点。
(回想一下，二叉搜索树是二叉树的一种，其每个节点都满足以下规则，对于 node.left 的任何后代，值总 < node.val，而 node.right 的任何后代，值总 > node.val。此外，先序遍历首先显示节点的值，然后遍历 node.left，接着遍历 node.right。）
示例： 输入：[8,5,1,7,10,12] 输出：[8,5,10,1,7,null,12]
解题思路：
与使用前中序，中后序构建二叉树类似，这里要构建的是二叉搜索树，其有一个特点就是，根节点的值大于左子节点的值，而小于右子节点的值，因此我们可以根据这个性质，将preorder分开，已知根节点为preorder[0]，则其左子树一定都小于这个值，并且均为连续的序列！因此我们可以使用lower_bound去查找刚好大于等于preorder[0]的值，将整个序列分开，从而变成两个子问题分别构建左子树和右子树！
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* bstFromPreorder(vector<int>& preorder) {
if(preorder.size() == 0) return nullptr;
TreeNode* root = new TreeNode(preorder[0]);
auto it = lower_bound(preorder.begin()+1, preorder.end(), preorder[0]);
vector<int> preleft(preorder.begin()+1, it);
vector<int> preright(it, preorder.end());
root->left = bstFromPreorder(preleft);
root->right = bstFromPreorder(preright);
return root;
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/construct-binary-search-tree-from-preorder-traversal
【LeetCode #129】求根到叶子节点数字之和
给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。 例如，从根到叶子节点路径 1->2->3 代表数字 123。 计算从根到叶子节点生成的所有数字之和。 说明: 叶子节点是指没有子节点的节点。
示例 1: 输入: [1,2,3] 1 / \ 2 3 输出: 25 解释: 从根到叶子节点路径 1->2 代表数字 12. 从根到叶子节点路径 1->3 代表数字 13. 因此，数字总和 = 12 + 13 = 25.
解题思路：
使用dfs算法，递归的遍历每条路径，这个算法虽然有点复杂，但可以很轻松的拓展到其他问题！至于如何拓展，请看下题~
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> res;
void dfs(TreeNode* root, int tmp){
tmp += root->val;
if(root->left == nullptr && root->right == nullptr){
res.push_back(tmp);
return;
}
if(root->left != nullptr)
dfs(root->left, tmp*10);
if(root->right != nullptr)
dfs(root->right, tmp*10);
}
int sumNumbers(TreeNode* root) {
if(root == nullptr) return 0;
int sum = 0;
dfs(root, 0);
for(auto i: res){
sum += i;
}
return sum;
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sum-root-to-leaf-number
【LeetCode #113】路径总和 II
解题思路：
与上面题目的递归形式是一样的，区别时，我们在判断和的值之后要把遍历的节点进行保存！
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> res;
vector<int> tmp;
void dfs(TreeNode* root, int sum){
tmp.push_back(root->val);
if(root->left == nullptr && root->right == nullptr && sum == root->val){
res.push_back(tmp);
return;
}
if(root->left != nullptr){
dfs(root->left, sum-root->val);
tmp.pop_back();
}
if(root->right != nullptr){
dfs(root->right, sum-root->val);
tmp.pop_back();
}
}
vector<vector<int>> pathSum(TreeNode* root, int sum) {
if(root == nullptr) return res;
dfs(root, sum);
return res;
}
};