1. 513.找树左下角的值
递归法,我考虑了一个情况,如果最后一行只有一个右孩子,其实也符合题意,因为最后一行没别的,他就是最左边.
其实递归法确定哪个顺序遍历后,模板套上去,比如先左后右,剩下的就是看要存什么,要借助哪些辅助变量来实现第三步的逻辑
比如这道题,用递归确定是不是最后一行的话,你就得知道他的深度,depth就得有,你还得和最大深度比较,因为如果可能左子树的最大深度是2,到了右子树成3了,因此要有maxDepth 和 curDepth.
- 法2 如果用迭代呢?
迭代就是BFS,一层一层走,while用来看这层走完没,进了while先把这层的长度冻结,然后让for走这段距离,这样就把这层走完了
那关于具体的操作最左边的呢?for就是遍历每一层,i===0就是最左边的节点
2. 112 路径总和
自己做出来了.和前面的找所有路径的如出一辙.
关键点就是在他是怎么解决分叉路口的.
当时的那道题是先处理中,也就是设置node.val+'->'把当前路径冻结,传进下一次的递归中.比如当前是1->,在分叉路口的时候,左节点和右节点传进去的都是1->,比如左节点就是叶子节点,对叶子节点的终止处理存到递归外定义好的res集中.
此题一样,一直递归增加值,叶子节点加上了如果刚好,就把在递归外定义的res改为true
3. 113.路径总和2
4.从中序和后序遍历序列构造二叉树
先看清题目.人给的是数组,不是表现成数组的二叉树.
所以中序后序就是左中右,左右中的存放模式.
特点:
- 后序: 最后一个一定是根节点.(切割后的某子树也一样,切出来的那一堆的最后一个就是子树的根节点.)
- 中序:找到根节点的话,左边就是左子树,右边就是右子树.
写的时候碰到的问题:
对于左子树,后序的个数拿的和中序的一样,因为
