算法学习之二叉树所有的路径

Jackey C/C++ 1,178 次浏览 , 没有评论

题目要求:

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

叶子节点 是指没有子节点的节点。

示例 1:

输入:root = [1,2,3,null,5]
输出:["1->2->5","1->3"]
示例 2:

输入:root = [1]
输出:["1"]
提示:

树中节点的数目在范围 [1, 100] 内
-100 <= Node.val <= 100

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-tree-paths

解题代码:

//Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;

        if (root == NULL)
            return res;

        if (root->left == NULL && root->right == NULL) {
            res.push_back(to_string(root->val));
            return res;
        }

        vector<string> leftS = binaryTreePaths(root->left);
        for (int i = 0; i < leftS.size(); ++i) {
            res.push_back(to_string(root->val) + "->" + leftS[i]);
        }

        vector<string> leftR = binaryTreePaths(root->right);
        for (int i = 0; i < leftR.size(); ++i) {
            res.push_back(to_string(root->val) + "->" + leftR[i]);
        }

        return res;
    }
};

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

Go