北京比较好的网站开发公司,网站页面优化工具,久久建筑网图集免费下载,网络安装目录
1 114. 二叉树展开为链表
2 105. 从前序与中序遍历序列构造二叉树
3 437. 路径总和 III 菜鸟做题#xff08;即将返校版#xff09;#xff0c;语言是 C 1 114. 二叉树展开为链表
题眼#xff1a;展开后的单链表应该与二叉树 先序遍历 顺序相同。 而先序遍历就…目录
1 114. 二叉树展开为链表
2 105. 从前序与中序遍历序列构造二叉树
3 437. 路径总和 III 菜鸟做题即将返校版语言是 C 1 114. 二叉树展开为链表
题眼展开后的单链表应该与二叉树 先序遍历 顺序相同。 而先序遍历就是指先遍历左子树再遍历右子树。题意所说的展开无非就是让左子树插队到右子树的前面去。 解题思路采用递归对于每个节点先将它的左子树链到右侧去再让右子树链到左子树的后面。
思路说明图 对于节点 “1”绿色部分为其左子树黄色部分为其右子树。我们需要做的就是先将左子树链到 “1” 的右侧去再让右子树链到左子树的后面。对于节点 “2”同理。
class Solution {
public:void flatten(TreeNode* root) {if (!root) return;TreeNode * p root-left;if (p) {while (p-right) {p p-right;}TreeNode * q root-right;root-right root-left;root-left nullptr; // heap-use-after-free on address 0x503000000138p-right q;}flatten(root-right);}
};
说明为了能使右子树链到左子树的屁股后面我们需要找到左子树的屁股代码如下。
while (p-right) {p p-right;
}
坑点题目中说 “左子指针始终为 null”即移走左子树后要把左子指针置为空指针代码如下。
root-left nullptr; // heap-use-after-free on address 0x503000000138 否则会出现注释中的报错。 2 105. 从前序与中序遍历序列构造二叉树
遍历特点
前序根节点 左子树 右子树中序左子树 根节点 右子树
因此preorder 和 inorder 数组中的元素也呈现出上述排列规律。
思路说明图 对于 preorder 数组根据遍历特点显然最左侧的 “3” 是根节点root。但是我们无法根据 preorder 数组得知 “3” 的左子树和右子树分别是哪两坨。这时inorder 数组就派上用场了。我们在 inorder 数组中定位 “3”根据遍历特点“3” 的左侧部分就是左子树“9”右侧部分就是右子树“20” “15” “7”。
现在我们知道 “3” 的左子树和右子树分别是什么了以及它们各自的长度。由此我们可以在 preorder 数组中得到 “3” 的左子树和右子树所处的区间即上图中的 绿色 部分和 蓝色 部分。又根据遍历特点我们知道 绿色 部分的最左侧是左子树的根节点root-left蓝色 部分的最左侧是右子树的根节点root-right。
以此类推构造整个二叉树。 综上preorder 数组的作用是定位各个根节点inorder 数组的作用是定位左子树和右子树。 参数说明
pre_left、pre_right当前子树在 preorder 数组所处的区间in_left、in_right当前子树在 inorder 数组所处的区间sub_ltree左子树长度帮助定位左子树区间
class Solution {
public:vectorint preorder, inorder;unordered_mapint, int hash;TreeNode * helper(int pre_left, int pre_right, int in_left, int in_right) {if (pre_left pre_right) return nullptr;int pre_root pre_left;int in_root hash[preorder[pre_root]];int sub_ltree in_root - in_left;TreeNode * node new TreeNode(preorder[pre_root]);node-left helper(pre_left 1, pre_left sub_ltree,in_left, in_root - 1);node-right helper(pre_left sub_ltree 1, pre_right,in_root 1, in_right);return node;}TreeNode* buildTree(vectorint arr1, vectorint arr2) {int n arr1.size();preorder arr1;inorder arr2;for (int i 0; i n; i) {hash[inorder[i]] i;}return helper(0, n - 1, 0, n - 1);}
}; 3 437. 路径总和 III
关键字深度搜索先序遍历 前缀和 我百度了一下说它俩是一个意思。我觉得采用先序遍历是因为它每次都是沿着一条直线去遍历的而不是像中序遍历那样跳着遍历的。因此先序遍历更符合题意。 思路说明图路径 “5, 3” 的和可以看作是路径 “10, 5, 3” 的和减去路径 “10” 的和也就是可以转换为字符串那一节的前缀和问题。 这里说的前缀是指以根节点为开始的路径而前缀和就是各个前缀的路径和。 具体解法
① 定义变量
hash 用于存放各个前缀的路径和total 用于记录当前加总出的路径和count 用于记录符合条件的路径和的个数
② 查询符合条件的路径和
if (hash.count(total - targetSum)) {count hash[total - targetSum];
} 就是在 hash 表中寻找是否有前缀的路径和与当前路径和的差为 targetSum 值。 ③ 先序遍历
hash[total];
count helper(root-left, total, targetSum);
count helper(root-right, total, targetSum);
hash[total]--; 在走向下一个节点之前先把当前路径和存入 hash 表中因为它是前缀和。同时当基于这条路径的所有路径都被遍历完毕后要把这条路径的路径和移出 hash 表即 hash[total]-- 。 比如我们遍历完了节点 “3” 及其左右子树接下来就该遍历 “5” 的右子树了。而 “5” 的右子树不会经过路径 “10, 5, 3” 。因此在节点 “3” 发现自己的左右子树被遍历完时“3” 就应该回收以自己为终点的路径 “10, 5, 3” 了。 class Solution {
public:unordered_maplong, int hash;int helper(TreeNode * root, long total, int targetSum) {if (!root) return 0;int count 0;total root-val;if (hash.count(total - targetSum)) {count hash[total - targetSum];}hash[total];count helper(root-left, total, targetSum);count helper(root-right, total, targetSum);hash[total]--;return count;}int pathSum(TreeNode* root, int targetSum) {hash[0] 1;return helper(root, 0, targetSum);}
};
说明下述代码是为了处理前缀本身的路径和等于 targetSum 的情况也就是它被减数不需要和另一个前缀减数做减法。这里用路径和为 0 来表示减数否则这种情况会被忽略。
hash[0] 1; 题外话虽然 count 变量在每一次递归中都是重新定义的但是因为它是返回值所以还是能起到计数器的作用。而 total 变量是作为参数一层一层传下去的所以它也能起到计数器的作用。
