Summary of the "binary tree path" problems, find the similarity yourself.(C++, DFS)


  • 0
    N

    The idea is just similar to the backtracking. Let me show you the code:

    1. Binary Tree Paths
        vector<string> binaryTreePaths(TreeNode* root) 
        {
            vector<string> ans;
            string path;
            dfs(ans, path, root);
            return ans;
        }
        
        void dfs(vector<string>& ans, string& path, TreeNode* t)
        {
            if (t == NULL)
                return;
            
            path += to_string(t->val) + "->";
            if (t->left == NULL && t->right == NULL)
                ans.push_back(path.substr(0, path.size() - 2));
            
            dfs(ans, path, t->left);
            dfs(ans, path, t->right);
            
            path.erase(path.end() - 2 - to_string(t->val).size(), path.end());
        }
    
    1. Sum Root to Leaf Numbers
        int sumNumbers(TreeNode* root) 
        {
            int ans = 0;
            int path = 0;
            dfs(ans, path, root);
            return ans;
        }
        
        void dfs(int& ans, int& path, TreeNode* t)
        {
            if (t == NULL)
                return;
            
            path = path * 10 + t->val;
            // reach the leaf node
            if (t->left == NULL && t->right == NULL)
                ans += path;
            
            dfs(ans, path, t->left);
            dfs(ans, path, t->right);
            
            path = (path - t->val) / 10;
        }
    
    1. Path Sum II
        vector<vector<int>> pathSum(TreeNode* root, int sum) 
        {
            vector<vector<int>> ans;
            vector<int> path;
            dfs(ans, path, root, sum);
            return ans;
        }
        
        void dfs(vector<vector<int>>& ans, vector<int>& path, TreeNode* t, int sum)
        {
            if (t == NULL)
                return;
            
            path.push_back(t->val);
            if (t->left == NULL && t->right == NULL && sum == t->val)
                ans.push_back(path);
            
            dfs(ans, path, t->left, sum - t->val);
            dfs(ans, path, t->right, sum - t->val);
            path.pop_back();
        }
    

    If you find other problems that can also be solved by the same way, just let me know.


Log in to reply
 

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