二叉树逐层删叶子节点：current=null赋值无效求助（LeetCode336）

问题需求 #

给定二叉树根节点，反复收集并删除所有叶子节点，直至树为空，最终输出每一轮收集到的叶子节点值组成的二维数组。

无效解法（问题排查） #

class Solution {
public:
    vector<vector<int>> findLeaves(TreeNode* root) {
         vector<vector<int>> result;
         if(root == NULL) return result;
 
        queue<TreeNode*> bfs;
       
        vector<int> leaves;
    
       while(root){
           
        bfs.push(root);
        while(!bfs.empty()){
            
        TreeNode* current = bfs.front();
        bfs.pop();
            
           
             if(current->left != nullptr) bfs.push(current->left);
             if(current->right != nullptr) bfs.push(current->right);
            
        
             if(current->left == nullptr && current->right == nullptr){
                leaves.push_back(current->val);
                 // 无法将叶子节点设为NULL
                 current = NULL;
             }              
        }
           result.push_back(leaves);
           leaves.clear();
    
           
        }
        return result;
        
    }
};

无效原因 #

这段代码的核心问题出在current = NULL这一行：

• current是局部指针变量，仅拷贝了队列中节点的地址。给current赋值NULL只是修改了这个局部变量，完全没改动原二叉树里父节点指向该叶子节点的指针（比如父节点的left或right成员）。
• 原树结构丝毫未变，每一轮循环都会重复收集同一批叶子节点，陷入死循环，根本无法真正删除叶子节点推进流程。

有效解法 #

class Solution {
public:
bool isLeaf(TreeNode* current){
        
        if(current->left  == NULL && current->right == NULL) return true;
        else 
        return false;
        
    }
    vector<vector<int>> findLeaves(TreeNode* root) {
        
        
        vector<vector<int>> result;
        
        if(root == NULL) return result;
        
        queue<TreeNode*> bfs;
        
        vector<int> leaves;
        
       // bfs.push(root);
        
        
        while(root != NULL){
            if(isLeaf(root)){
                leaves.push_back(root->val);
                root = nullptr;
            }
            else {
                
                bfs.push(root);
            }
            
            
            while(!bfs.empty()){
                
                TreeNode* current = bfs.front();
                bfs.pop();
                
                
                if(current->left && isLeaf(current->left)){
                    leaves.push_back(current->left->val);
                    current->left = nullptr;
                }
                else if(current->left){
                    bfs.push(current->left);
                }
                
                
                 if(current->right && isLeaf(current->right)){
                    leaves.push_back(current->right->val);
                    current->right = nullptr;
                }
                else if(current->right){
                    bfs.push(current->right);
                }
                
                
            }
            result.push_back(leaves);
            leaves.clear();            
        }
        return result;
        
        
    }
};

有效原理 #

有效解法的核心是直接修改父节点的指针成员：

• 遍历过程中不直接操作叶子节点本身，而是检查当前节点的左、右子节点是否为叶子节点。
• 如果是叶子节点，就将父节点对应的left或right赋值为nullptr，直接修改原二叉树结构，真正删除该叶子节点。
• 若根节点本身是叶子节点，直接将root赋值为nullptr，结束循环。

内容的提问来源于stack exchange，提问作者Christopher Stone