一、513.找树左下角的值
题目链接：
学习前：
思路：
层序遍历。采用递归和迭代两种方式
- 递归：定义最大深度和目标值两个成员变量，方法参数是结点和当前结点的深度；返回类型为void；终止条件为结点为空；单次循环内容为判断该节点是否符合目标要求，且分别传入左子树和右子树，且深度分别加一，进行递归调用
- 迭代：new一个队列，存层次遍历的结点，取每一层的第一个结点值进行赋值，遍历结束后即为所求
学习后：
进行代码优化。对于递归，判断该节点是否符合目标要求作为终止条件，且在递归调用左子树和右子树时进行判空
二、112. 路径总和
题目链接：
学习前：
思路：
前序遍历。采用递归方式
- 递归：定义sum累加从根结点到叶子结点的和
- 方法参数：(TreeNode root, int targetSum, int sum)
- 返回类型：boolean
- 终止条件：结点为空返回false；碰到叶子结点，满足目标返回true，反之返回false
- 单次循环内容：首先在终止条件之间加入sum累加当前结点值，接着此时的结点一定非空且非叶子结点，故若左子树存在，则递归调用左孩子，若结果返回true，则返回true；右子树同理；本次循环若在这些地方都没返回，则返回false
学习后：
- 不用额外定义sum，直接用targetSum做减法，判断是否为0即可
三、113.路径总和ii
题目链接：
学习前：
思路：
前序遍历。采用递归方式
-
递归：定义sum累加从根结点到叶子结点的和
- 方法参数：(TreeNode root, int targetSum)，其中成员变量List res是结果集合，成员变量List per是单条路径值集合
- 返回类型：void
- 终止条件：结点为空；碰到叶子结点，其中若符合题意则res.add
- 单次循环内容：若左右孩子存在，则分别进行递归调用，且回溯per，删除最后一个元素
学习后：
将成员变量List res和List per降为方法参数，减小内存开销
四、106.从中序与后序遍历序列构造二叉树
题目链接：
学习前：
思路：
递归
- 方法参数：(int[] inorder, int[] postorder)
- 返回类型：TreeNode
- 终止条件：if(inorder.length0) return null;if(inorder.length1) return root;
- 单次循环内容：
- 确定根结点即后序遍历最后一个值
- 找到中序遍历的根结点下标index
- 根据index将中序遍历切割成左中序和右中序两个数组
- 根据第3步切割的数组的长度将后序遍历切割成左后序和右后序两个数组
- 递归调用
学习后：
- 在对中序数组和后续数组进行切割时，不用再额外开辟新数组，通过下标进行访问，即方法参数变为(int[] inorder, int inorder_start, int inorder_end, int[] postorder, int postorder_start, int postorder_end)
- 注意对终止条件和单次循环内容的改写
五、105.从前序与中序遍历序列构造二叉树
题目链接：
学习后：
思路：
递归
- 方法参数：(int[] preorder， int[] inorder)
- 返回类型：TreeNode
- 终止条件：if(inorder.length0) return null;if(inorder.length1) return root;
- 单次循环内容：
- 确定根结点即前序遍历第一个值
- 找到中序遍历的根结点下标index
- 根据index将中序遍历切割成左中序和右中序两个数组
- 根据第3步切割的数组的长度将前序遍历切割成左前序和右前序两个数组
- 递归调用
六、学习总结
- 时间：5.5h
- 通过遍历顺序构建唯一二叉树
- 递归需要返回值和无需返回值的情况