My java and c++ solution,c++ 4ms


  • 14
    N

    this is a simple dfs+tree question,using preorder to visit tree will be fine.

    c++:

     class Solution {
        public:
        
                vector<string> binaryTreePaths(TreeNode* root) {
                    vector<string> v;
                    if(root)
                        preorder(v,root,"");
                    return v;
                }
                void preorder(vector<string>& v,TreeNode* r,string t){
                    if(!r)
                        return;
                    if(!t.empty())
                        t+=("->"+to_string(r->val));
                    else t+=to_string(r->val);
                    if(r->left||r->right){
                        preorder(v,r->left,t);
                        preorder(v,r->right,t);
                    }else{
                        v.push_back(t);
                    }
                }
            };
    

    my java:

    public class Solution {
        public List<String> binaryTreePaths(TreeNode root) {
            List<String> l=new ArrayList<>();
            if(root!=null)
                pre(l,root,"");
            return l;
        }
         void pre(List<String> l,TreeNode r,String s){
             if(r==null)return;
             if(s.isEmpty())
                s+=r.val;
            else s+=("->"+r.val);
            if(r.left!=null||r.right!=null){
                pre(l,r.left,s);
                pre(l,r.right,s);
            }else
                l.add(s);
         }
    }

  • 1
    P

    What is the complexity of your solution?


  • 1
    M

    IMHO, pre() functions are called estimated #(nodes) times, each call include O(1) operations, so it is O(n) complexity. Am I right?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.