代码随想录算法训练营第十八天 | 513.找树左下角的值、112. 路径总和、113. 路径总和ii

本文主要是介绍代码随想录算法训练营第十八天 | 513.找树左下角的值、112. 路径总和、113. 路径总和ii，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接: 513.找树左下角的值
链接: 112. 路径总和，和 113. 路径总和ii
链接: 从中序与后序遍历序列构造二叉树

自己看到题目的第一想法

513.找树左下角的值：层序遍历，输出最后一行的最左边的值。自己亲手写代码之后发现，有个问题就是，你怎么知道此时就是最后一层呢？另一种方法是递归法，采用后序遍历，递归处理逻辑是当中间节点的左叶子节点的子节点都为空的时候返回该左叶子节点的值。自己亲手写代码之后发现编译错误，缺少return语句。
112.路径总和和 113.路径总和ii：使用递归法用三部曲思考，第一返回类型和参数，返回类型应该是boolean，判断是否为路径和，参数输入应该是首先是根节点，其次是路径和targetSum；第二步是递归函数的终止条件，如果遍历完成路径和加起来等于targetSum则返回true，否则为false；第三步是递归的逻辑。113.路径总和ii我觉得在上面的基础上再增加一个记录节点路径的数组就好。

看完代码随想录之后的想法

513.找树左下角的值：看完答案之后发现，在迭代法也就是层序遍历过程中，你只需要记录每一层的最左边的节点的值，然后每一层每一层会覆盖掉，那么最终结束的时候你得到的就是最后一层的最左边的值。第二个关于自己写的错误代码，发现自己其实对于左侧理解有错误，左侧不一定必须是左叶子节点，只要是每一层的从左往右第一个就算是最左侧。并且对于卡哥的回溯，我觉得蛮复杂，我看力扣上关于递归进行深度优先搜索很简单。就是每递归一次也就是每往下进行探索一次，都对深度进行加1，但是我看没有进行回溯。之后看了视频知道这是递归中隐藏了回溯。这好复杂。

// 力扣深度优先搜索
class Solution {int curVal = 0;int curHeight = 0;public int findBottomLeftValue(TreeNode root) {int curHeight = 0;dfs(root, 0);return curVal;}public void dfs(TreeNode root, int height) {if (root == null) {return;}height++;dfs(root.left, height);dfs(root.right, height);if (height > curHeight) {curHeight = height;curVal = root.val;}}
}// 卡哥递归法
class Solution {private int Deep = -1;private int value = 0;public int findBottomLeftValue(TreeNode root) {value = root.val;findLeftValue(root,0);return value;}private void findLeftValue (TreeNode root,int deep) {if (root == null) return;if (root.left == null && root.right == null) {if (deep > Deep) {value = root.val;Deep = deep;}}if (root.left != null) findLeftValue(root.left,deep + 1);if (root.right != null) findLeftValue(root.right,deep + 1);}
}

路径总和：看了卡哥视频觉得里面学问可真多，递归顺序，回溯等等都要考虑，我觉得目前我的水平看懂回溯确实困难，看了力扣觉得还蛮简单，前序遍历，如果根节点是Null直接返回false，每次递归都将targetSum-遍历的root.val，如果遍历到叶子节点就返回是否该节点的值等于targetSum。
113.路径总和ii：首先，返回的是一个二维数组，那么底层用什么实现呢？结合之前学过的知识，链表这种数据结构的增删查改效率比较高，对于数组不断改变且初始长度并不明确的情况，最好采用链表进行创建和声明。其次，声明了一个双端队列来辅助记录路径。关于双端队列里采用到的api有如下：

path.offerLast(root.val);//在队尾增加元素值
path.pollLast();//队尾元素出队

思路就是，枚举每一条从根节点到叶子节点的路径，当和为targetSum的时候就找到了。
从中序与后序遍历序列构造二叉树:总体思想还蛮简单，根据后序或者前序确定根节点之后去切中序，分割之后利用左子序去切割后序或者前序得到两个子序，之后再利用后序得到根节点····递归。

自己实现过程中遇到哪些困难

1.切割是怎么算切割了？代码如何写？
2.区间如何区分
3.java中用到了map，体会妙处

这篇关于代码随想录算法训练营第十八天 | 513.找树左下角的值、112. 路径总和、113. 路径总和ii的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---