一、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
- 通过遍历顺序构建唯一二叉树
- 递归需要返回值和无需返回值的情况