二叉树的所有路径
题解:
这道题要求从根节点到叶子的路径,所以需要前序遍历,这样才方便让父节点指向孩子节点,找到对应的路径,因此涉及到了回溯。
1.递归函数及返回值
传入根节点,记录每一条路径的path,存放结果集的result,不需要返回值
2.确定递归终止条件
当左右孩子都为空的时候
3.确定单层递归逻辑
因为是前序遍历,需要先处理中间节点,中间节点间就是我们要记录路径上的节点,先放进path,然后递归和回溯的过程。回溯和递归是一一对应的,有一个递归,就要有一个回溯。
代码:
左叶子之和
题解:
左叶子的明确定义:节点A的左孩子不为空,且左孩子的左右孩子都为空。判断条件:if root.left and not root.left.left and not root.left.right
通过后序遍历实现,因为要通过递归函数的返回值来累加求取左叶子数值之和。
1.确定递归函数的参数和返回值
传入树的根节点,返回的是数值之和
2.终止条件
根节点是空,左叶子值一定是0
根节点的左右孩子为空,左叶子值一定是0
3.确定单层递归的逻辑
当遇到左叶子节点的时候,记录数值,然后通过递归求取左子树左叶子之和,和右子树左叶子之和,相加便是整个树的左叶子之和
代码: