How can I remove the root?


  • 2

    I know how to remove children - set the parent's left or right to null. But how can I remove the root?


  • 0
    L

    By introducing a "fakeRoot"?

    public class Solution {
        public List<List<Integer>> findLeaves(TreeNode root) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            
            TreeNode fakeRoot = new TreeNode(0);
            fakeRoot.right = root;
            
            while(fakeRoot.right != null){
                List<Integer> current = new ArrayList<Integer>();
                dfs(current, fakeRoot);
                result.add(current);
            }
            
            return result;
        }
        
        private boolean dfs(List<Integer> current, TreeNode node){
            if(node == null){
                return false;
            }else{
                if(node.left == null && node.right == null){
                    return true;
                }else{
                    if(dfs(current, node.left)){
                        current.add(node.left.val);
                        node.left = null;
                    }
                    if(dfs(current, node.right)){
                        current.add(node.right.val);
                        node.right = null;
                    }
                    return false;
                }
            }
        }
    }

  • 0
    L

    If you mean to make the root collectable, probably it will not happen as long as the caller still holds the reference ?


  • 0
    Q

    Hi @StefanPochmann, I created a dummy root whose left child is root and right child is NULL.
    See my C++ implementation:
    https://leetcode.com/discuss/110449/0ms-c-dfs-solution-with-dummy-root


  • 0

    Doesn't remove the root from the given tree but from your extra thing. The caller will end up with a one-node tree, not an empty tree. So this isn't doing the whole requested job.


  • 0

    @qiangxitan@gmail.com Doesn't remove the root from the given tree but from your extra thing. The caller will end up with a one-node tree, not an empty tree. So this isn't doing the whole requested job.


  • 0
    R

    I first find the leaf nodes and insert their value in a vector. After this, I make them NULL. As I call the nodes using reference, the root eventually gets deleted.

    void find(TreeNode* &root, vector<int> &leaves)
        {
            if(root==NULL)
                return;
            if(root->left==NULL && root->right==NULL)
            {
                leaves.push_back(root->val);
                root=NULL;
                return;
            }
            find(root->left,leaves);
            find(root->right,leaves);
        }
        vector<vector<int>> findLeaves(TreeNode* root) {
            vector<vector<int>> all;
            vector<int> leaves(0);
            while(root)
            {
                find(root,leaves);
                all.push_back(leaves);
                leaves.clear();
            }
            return all;
        }
    

Log in to reply
 

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