在这里插入图片描述


LeetCode257.二叉树的所有路径


题目:

  • 给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。叶子节点 是指没有子节点的节点。

示例:

在这里插入图片描述

  • 输入: r o o t = [ 1 , 2 , 3 , n u l l , 5 ] root = [1,2,3,null,5] root=[1,2,3,null,5]
  • 输出: [ " 1 − > 2 − > 5 " , " 1 − > 3 " ] ["1->2->5","1->3"] ["1−>2−>5","1−>3"]

解题思路一:(递归)

  1. 确定递归函数的参数和返回值:

    传入当前节点、结果集、路径集,采用引用方式传递,无需返回值。

    void dfs(TreeNode* cur, vector<string>& res, vector<int>& path)
    
  2. 确定终止条件:

    每遍历一个节点就先将其加入到路径集中,然后判断该节点左右孩子是否都为空,若都为空代表到达了叶子节点,进行相应处理与返回。

    path.push_back(cur->val);
    if(cur->left == NULL && cur->right == NULL){
        string subPath = "";
        for(int i = 0; i < path.size(); i++){
            subPath += to_string(path[i]);
            if(i == path.size() - 1) break;
            subPath += "->";
        }
        res.push_back(subPath);
        return;
    }
    
  3. 确定单层递归逻辑:

    递归左右子树,需要对path进行回溯。

    if(cur->left){
        dfs(cur->left, res, path);
        path.pop_back();
    }
    if(cur->right){
        dfs(cur->right, res, path);
        path.pop_back();
    } 
    

C++版整体代码

class Solution {
public:
    void dfs(TreeNode* cur, vector<string>& res, vector<int>& path){
        // 每递归遍历一个节点,就将其加入到路径集中待后续处理使用
        path.push_back(cur->val);
        // 当递归遍历到叶子节点,进行处理
        if(!cur->left && !cur->right){
            string tempStr = "";
            for(int i = 0; i < path.size(); i++){
                tempStr += to_string(path[i]);
                if(i == path.size() - 1) break;
                tempStr += "->";
            }
            res.push_back(tempStr);
            return;
        }
        if(cur->left){
            dfs(cur->left, res, path);
            path.pop_back();
        }
        if(cur->right){
            dfs(cur->right, res, path);
            path.pop_back();
        }
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        vector<int> path;
        if(!root) return res;
        dfs(root, res, path);
        return res;
    }
};

Java实现版本

class Solution {
    public void dfs(TreeNode cur, List<String> res, List<Integer> path){
        path.add(cur.val);
        if(cur.left == null && cur.right == null){
            String tempStr = "";
            for(int i = 0; i < path.size(); i++){
                tempStr += String.valueOf(path.get(i));
                if(i == path.size() - 1) break;
                tempStr += "->";
            }
            res.add(tempStr);
            return;
        }
        if(cur.left != null){
            dfs(cur.left, res, path);
            path.remove(path.size() - 1);
        }
        if(cur.right != null){
            dfs(cur.right, res, path);
            path.remove(path.size() - 1);
        }
    }
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        if(root == null) return res;
        dfs(root, res, path);
        return res;
    }
}

更多推荐