。

具体的实现可以使用队列来存储每一层的节点#xff0c;并且在遍历每一层节点时#xff0c;不断更新最左边的节点的值。

…一、513.找树左下角的值

这个题目的主要思路是使用广度优先搜索BFS遍历整棵树最后返回最后一层的最左边的节点的值。

具体的实现可以使用队列来存储每一层的节点并且在遍历每一层节点时不断更新最左边的节点的值。

时间复杂度为O(n)其中n是节点的个数。

二、112.路径总和

这个题目的主要思路是使用深度优先搜索DFS遍历整棵树同时记录到达每个节点时的路径和如果到达叶子节点时路径和等于给定的目标和则返回true。

具体的实现可以使用递归来实现DFS同时在每个节点处更新路径和并且在到达叶子节点时判断路径和是否等于目标和。

时间复杂度为O(n)其中n是节点的个数。

三、113.路径总和ii

这个题目的主要思路和112题类似也是使用DFS遍历整棵树同时记录到达每个节点时的路径和并且在到达叶子节点时判断路径和是否等于给定的目标和。

不同的是这个题目需要返回所有满足条件的路径而不仅仅是返回true或false。

具体的实现可以在DFS的过程中使用一个数组来存储当前的路径并且在到达叶子节点时如果路径和等于目标和则将整个路径加入结果列表中。

时间复杂度为O(n^2)其中n是节点的个数主要是因为每次需要复制一份路径数组。

这个题目的主要思路是使用递归来构建整棵树。

具体的实现可以先找到后序遍历序列中的最后一个节点作为根节点然后在中序遍历序列中找到根节点的位置从而确定左子树和右子树的范围。

然后递归的构建左子树和右子树即可。

时间复杂度为O(n)其中n是节点的个数。

这个题目的主要思路和106题类似也是使用递归来构建整棵树。

具体的实现可以先找到前序遍历序列中的第一个节点作为根节点然后在中序遍历序列中找到根节点的位置从而确定左子树和右子树的范围。

然后递归的构建左子树和右子树即可。

时间复杂度为O(n)其中n是节点的个数。

public

LinkedList();queue.offer(root);int

res

{queue.offer(node.right);}}}return

res;

ArrayList(path));}dfs(root.left,

sum