万基城市建设有限公司网站,windows优化大师破解版,网站开发合同.doc,河南省建设厅官方网站郭风春目录题目分析递归法题目来源 257. 二叉树的所有路径
题目分析
前序遍历以及回溯的过程如图#xff1a;
递归法
1.递归函数参数以及返回值
要传入根节点#xff0c;记录每一条路径的path#xff0c;和存放结果集的result#xff0c;这里递归不需要返回值#xff0c;代…
目录题目分析递归法题目来源 257. 二叉树的所有路径
题目分析
前序遍历以及回溯的过程如图
递归法
1.递归函数参数以及返回值
要传入根节点记录每一条路径的path和存放结果集的result这里递归不需要返回值代码如下
void traversal(TreeNode root, ListInteger paths, ListString res)2.确定递归终止条件
在写递归的时候都习惯了这么写
if (root null) {终止处理逻辑
}但是本题的终止条件这样写会很麻烦因为本题要找到叶子节点就开始结束的处理逻辑了把路径放进result里。 那么什么时候算是找到了叶子节点 是当 root不为空其左右孩子都为空的时候就找到叶子节点。 所以本题的终止条件是
if (root.left null root.right null) {终止处理逻辑
}这里我们先使用List结构的path容器来记录路径那么终止处理逻辑如下 if (root.left null root.right null) {// 输出StringBuilder sb new StringBuilder();// StringBuilder用来拼接字符串速度更快for (int i 0; i paths.size() - 1; i) {sb.append(paths.get(i)).append(-);}sb.append(paths.get(paths.size() - 1));// 记录最后一个节点res.add(sb.toString());// 收集一个路径return;}3.确定单层递归逻辑
因为是前序遍历需要先处理中间节点中间节点就是我们要记录路径上的节点先放进path中。
paths.add(root.val);// 前序遍历中然后是递归和回溯的过程上面说过没有判断root是否为空那么在这里递归的时候如果为空就不进行下一层递归了。 所以递归前要加上判断语句下面要递归的节点是否为空如下 if (root.left ! null) { // 左traversal(root.left, paths, res);}if (root.right ! null) { // 右traversal(root.right, paths, res);}此时还没完递归完要做回溯啊因为path 不能一直加入节点它还要删节点然后才能加入新的节点。 那么回溯要怎么回溯呢一些同学会这么写如下 if (root.left ! null) { // 左traversal(root.left, paths, res);}if (root.right ! null) { // 右traversal(root.right, paths, res);}paths.remove(paths.size() - 1);// 回溯这个回溯就有很大的问题我们知道回溯和递归是一一对应的有一个递归就要有一个回溯这么写的话相当于把递归和回溯拆开了 一个在花括号里一个在花括号外。 所以回溯要和递归永远在一起世界上最遥远的距离是你在花括号里而我在花括号外 那么代码应该这么写 // 递归和回溯是同时进行所以要放在同一个花括号里if (root.left ! null) { // 左traversal(root.left, paths, res);paths.remove(paths.size() - 1);// 回溯}if (root.right ! null) { // 右traversal(root.right, paths, res);paths.remove(paths.size() - 1);// 回溯}整体代码如下
class Solution {/*** 递归法*/public ListString binaryTreePaths(TreeNode root) {ListString res new ArrayList();// 存最终的结果if (root null) {return res;}ListInteger paths new ArrayList();// 作为结果中的路径traversal(root, paths, res);return res;}private void traversal(TreeNode root, ListInteger paths, ListString res) {paths.add(root.val);// 前序遍历中// 遇到叶子结点if (root.left null root.right null) {// 输出StringBuilder sb new StringBuilder();// StringBuilder用来拼接字符串速度更快for (int i 0; i paths.size() - 1; i) {sb.append(paths.get(i)).append(-);}sb.append(paths.get(paths.size() - 1));// 记录最后一个节点res.add(sb.toString());// 收集一个路径return;}// 递归和回溯是同时进行所以要放在同一个花括号里if (root.left ! null) { // 左traversal(root.left, paths, res);paths.remove(paths.size() - 1);// 回溯}if (root.right ! null) { // 右traversal(root.right, paths, res);paths.remove(paths.size() - 1);// 回溯}}
}
