LeetCode #257 Binary Tree Paths

問題概要

入力値：root([int])
出力値：[string]
Given the root of a binary tree, return all root-to-leaf paths in any order.
問題のリンク

入力例

Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]

解答例1

計算量：O(n)
Python

class Solution(object):
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        result = []
        def search(root, cur, res):
            if not root.right and not root.left:
                res.append(cur+str(root.val))
            if root.left:
                search(root.left, cur+str(root.val) + "->", res)
            if root.right:
                search(root.right, cur+str(root.val) + "->", res)
        search(root, "", result)
        return result

Runtime: 13ms
Beats: 75.55%

C++

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

    void search(TreeNode* root, string cur, vector<string>& result) {
        if (!root->left && !root->right) {
            result.push_back(cur+to_string(root->val));
        }
        if (root->left) {
            search(root->left, cur+to_string(root->val)+"->", result);
        }
        if (root->right) {
            search(root->right, cur+to_string(root->val)+"->", result);
        }
    }
};

Runtime: 0ms
Beats: 100%