0ms C++ DFS solution with dummy root


  • -1
    Q

    Using DFS to traverse to the leaf of the tree, add the leaf node to the temporary vector and using its parent node to set the leaf node to be NULL. Repeat the procedure until end.

    One trick is to use a dummy root and attach the real root as left child. This will make the while loop easy.

    vector<vector<int>> findLeaves(TreeNode* root) {
        vector<vector<int>> ret;
        if(!root) return ret;
        TreeNode dummy(0);
        dummy.left = root;
        
        while (dummy.left!=NULL) {
            vector<int> leaves;
            dfs(root, &dummy, true, leaves);
            ret.push_back(leaves);
        }
        return ret;
    }
    
    void dfs(TreeNode* root, TreeNode* parent, bool isLeft, vector<int>& leaves) {
        if (root->left==NULL && root->right==NULL) {
            leaves.push_back(root->val);
            if (isLeft) parent->left = NULL;
            else parent->right = NULL;
            return;
        }
        if (root->left) dfs(root->left, root, true, leaves);
        if (root->right) dfs(root->right, root, false, leaves);
        return;
    }

Log in to reply
 

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