Sharing my 16ms C++ non-recursive solution


  • 1
    L
    vector<vector<int> > pathSum(TreeNode* root, int sum)
    {
    vector<vector<int>> ret;
    vector<int> path;
    
    if(!root)
        return ret;
    
    int left_visited = 0;//0: not visited; 1: visited
    int right_visited = 0;
    TreeNode* cur = root;
    TreeNode* pre = NULL;
    stack<TreeNode*> s;
    s.push(cur);
    
    while(!s.empty())
    {
        cur = s.top();
        //计算当前结点的左右孩子是否被访问
        if((pre && pre == cur->left) || (pre == cur && cur->left == NULL))
            left_visited = 1;
        else
            left_visited = 0;
        if((pre && pre == cur->right) || (pre == cur && cur->right == NULL))
            right_visited = 1;
        else
            right_visited = 0;
    
        //只有当结点的左右孩子都没有访问过时,才加入路径中
        if(!left_visited && !right_visited)
            path.push_back(cur->val);
    
        //找到叶子结点,计算路径和,如果与sum相等,将该路径添加到ret
        if(!cur->left && !cur->right)
        {
            int calc = accumulate(path.begin(), path.end(), 0);
            if(calc == sum)
                ret.push_back(path);
            path.pop_back();
            s.pop();
        }
        else//若不是,分类讨论
        {
            //如果右孩子已经被访问过,则应该执行回溯了,因为使用了前序遍历的逻辑
            if(right_visited == 1)
            {
                path.pop_back();
                s.pop();
            }
            else//如果没有,应该先判断左孩子是否访问;先访问左孩子
            {
                if(left_visited == 0 && cur->left != NULL)
                    s.push(cur->left);
                else if(cur->right != NULL)
                    s.push(cur->right);
            }
        }
        pre = cur;
    }
    return ret;
    }
    

    代码解析见文章 Here is the analysis。使用了回溯法的思路,i consider it as a tracing-back problem


Log in to reply
 

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