257.二叉树的所有路径

曾经终败给现在 2023-10-15 22:22 4阅读 0赞

### 257.二叉树的所有路径 ###

*  题干描述
 *  解题思路
 *   *  1. 递归
     *   *  1.1 递归函数参数以及返回值
         *  1.2 确定递归终止条件
         *  1.3 确定单层递归逻辑
     *  2. 迭代法
 *  具体代码
 *   *  1. 递归法
     *   *  方式一
         *  方式二
     *  2. 迭代法

# 题干描述 #

[力扣入口-257. 二叉树的所有路径][-257.]

给定一个二叉树，返回所有从根节点到叶子节点的路径。

示例：  
![在这里插入图片描述][9d5df92e24984de6878fb7a8b7b34eb5.png]

# 解题思路 #

这道题目要求从根节点到叶子的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径。

在这道题目中将第一次涉及到回溯，因为我们要把路径记录下来，需要回溯来回退一个路径再进入另一个路径。

前序遍历以及回溯的过程如图：  
![在这里插入图片描述][9f4b143674fe429a91c70b5b3a362982.png]  
我们先使用递归的方式，来做前序遍历。**要知道递归和回溯就是一家的，本题也需要回溯**。

## 1. 递归 ##

### 1.1 递归函数参数以及返回值 ###

要传入根节点，记录每一条路径的path，和存放结果集的result，这里递归不需要返回值。

### 1.2 确定递归终止条件 ###

在写递归的时候都习惯了这么写：

if(cur == NULL){
        
    	终止处理逻辑
    }

但是本题的终止这样写会很麻烦，因为本题要找到叶子节点，就开始结束的处理逻辑了（把路径放进result里）。

**那么什么时候算是找到了叶子节点？**  
当cur不为空，其左右孩子都为空的时候，就找到了叶子节点。

所以本题的终止条件是：

if(cur->left == NULL && cur->right == NULL){
        
    	终止处理逻辑
    }

这里使用vector结构path来记录路径，所以要将vector结构的path转为string格式，再把这个string放进result里。

**那么为什么使用了vector结构来记录路径呢？**  
因为在下面处理单层递归逻辑的时候，要做回溯，**使用vector方便来做回溯**。

### 1.3 确定单层递归逻辑 ###

因为是前序遍历，需要先处理中间节点，中间节点就是我们要记录路径上的节点，先放进path中。

path.push_back(cur->val);

然后是递归和回溯的过程，上面说过没有判断cur是否为空，那么在这里递归的时候，如果为空就不进行下一层递归了。

所以递归前要加上判断语句，下面要递归的节点是否为空，如下：

if(cur->left){
        
    	traversal(cur->left, path, result);
    }
    if (cur->right) {
        
        traversal(cur->right, path, result);
    }

此时还没完，递归完，要做回溯，因为path不能一直加入节点，它还要删节点，然后才能加入新的节点。

一部分同学可能会这样写回溯：

if (cur->left) {
        
        traversal(cur->left, path, result);
    }
    if (cur->right) {
        
        traversal(cur->right, path, result);
    }
    path.pop_back();

这个回溯有一个很大的问题，回溯和递归是一一对应的，有一个递归，就要有一个回溯，所以需要将两者放在一起。

if (cur->left) {
        
        traversal(cur->left, path, result);
        path.pop_back(); // 回溯
    }
    if (cur->right) {
        
        traversal(cur->right, path, result);
        path.pop_back(); // 回溯
    }

## 2. 迭代法 ##

至于非递归的方式，我们依然可以使用前序遍历的迭代方式来模拟遍历路径的过程。

这里除了模拟递归需要一个栈，同时还需要一个栈来存放对应的遍历路径。

使用java的同学可以直接定义一个成员变量为object的栈`Stack<Object> stack = new Stack<>();`，这样就不用定义两个栈了，都放到一个栈就可以了。

# 具体代码 #

## 1. 递归法 ##

### 方式一 ###

// 257.二叉树的所有路径 - 递归法（方式一）
    public List<String> binaryTreePaths(TreeNode root){
        
        List<String> res = new ArrayList<>(); // 存最终的结果
        if(root == null){
        
            return res;
        }
        List<Integer> paths = new ArrayList<>(); // 作为结果中的路径
        traversal(root, paths, res);
        return res;
    }
    
    private void traversal(TreeNode root, List<Integer> paths, List<String> 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); // 回溯
        }
    }

### 方式二 ###

// 257.二叉树的所有路径 - 递归法（方式二）
    List<String> result = new ArrayList<>();
    
    public List<String> binaryTreePaths2(TreeNode root){
        
        deal(root, "");
        return result;
    }
    
    public void deal(TreeNode node, String s){
        
        if(node == null){
        
            return;
        }
        if(node.left == null && node.right == null){
        
            result.add(new StringBuilder(s).append(node.val).toString());
            return;
        }
        String tmp = new StringBuilder(s).append(node.val).append("->").toString();
        deal(node.left, tmp);
        deal(node.right, tmp);
    }

## 2. 迭代法 ##

public List<String> binaryTreePaths3(TreeNode root){
        
         List<String> result = new ArrayList<>();
         if(root == null)
             return result;
         Stack<Object> stack = new Stack<>();
         // 节点和路径同时入栈
         stack.push(root);
         stack.push(root.val + "");
         while(!stack.isEmpty()){
        
             // 节点和路径同时出栈
             String path = (String)stack.pop();
             TreeNode node = (TreeNode) stack.pop();
             // 若找到叶子节点
             if(node.left == null && node.right == null){
        
                 result.add(path);
             }
             // 右子节点不为空
             if(node.right != null){
        
                 stack.push(node.right);
                 stack.push(path + "->" + node.right.val);
             }
             // 左子节点不为空
             if(node.left != null){
        
                 stack.push(node.left);
                 stack.push(path + "->" + node.left.val);
             }
         }
         return result;
     }

**参考资料**：[257. 二叉树的所有路径][257.]

[-257.]: https://leetcode.cn/problems/binary-tree-paths/
[9d5df92e24984de6878fb7a8b7b34eb5.png]: https://img-blog.csdnimg.cn/9d5df92e24984de6878fb7a8b7b34eb5.png
[9f4b143674fe429a91c70b5b3a362982.png]: https://img-blog.csdnimg.cn/9f4b143674fe429a91c70b5b3a362982.png
[257.]: https://programmercarl.com/0257.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%89%80%E6%9C%89%E8%B7%AF%E5%BE%84.html