XTAO's Tech Blog
0%

[Leetcode]257. Binary Tree Paths(C++)

发表于 分类于 ， 评论数：
1k 1 分钟

题目描述

题目链接：257. Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.

例子

Input: [1,2,3,null,5]
Output: ["1->2->5", "1->3"]
Explanation: All root-to-leaf paths are: 1->2->5, 1->3

Note

  • A leaf is a node with no children.

解题思路

利用深度优先搜索，对每一个非空节点首先将其值加如路径中，如果该节点既没有左子树也没有又子树则表示是根节点，将当前路径存入结果中。否则递归遍历其左子树和右子树。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <string>
#include <vector>

class Solution {
public:
    std::vector<std::string> binaryTreePaths(TreeNode* root) {
        dfs(root, "");
        return paths;
    }

private:
    std::vector<std::string> paths;
    void dfs(TreeNode* root, std::string path) {
        if (!root) {
            return;
        }

        // 只有当路径非空时才需要加箭头
        if (!path.empty()) path += "->";
        path += std::to_string(root->val);
        if (!root->left && !root->right) {
            paths.push_back(path);
            return;
        }
        dfs(root->left, path);
        dfs(root->right, path);
    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(n) 额外空间来自所需空间，递归深度为二叉树最大深度

GitHub 代码同步地址： 257.BinaryTreePaths.cpp

其他题目：
GitHub: Leetcode-C++-Solution
博客： Leetcode-Solutions

推荐文章