返回

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

题目描述

题目链接: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.

解题思路

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

代码如下:

#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

Built with Hugo
Theme Stack designed by Jimmy