【MEDIUM】Find Leaves Of Binary Tree

发布于: 2019-03-05 23:24
阅读: 25
评论: 0
喜欢: 0

问题

原题链接:https://leetcode.com/problems/find-leaves-of-binary-tree/

Given a binary tree, collect a tree's nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.

Example:

Input: [1,2,3,4,5]
  
          1
         / \
        2   3
       / \     
      4   5    

Output: [[4,5,3],[2],[1]]

Explanation:

1. Removing the leaves [4,5,3] would result in this tree:

          1
         / 
        2          
 

2. Now removing the leaf [2] would result in this tree:

          1          
 

3. Now removing the leaf [1] would result in the empty tree:

          []         

分析过程

  • 输入:一棵二叉树
  • 输出:每次移除所有子节点,直到整棵树都是空的
  • 思路:递归判断节点是否是叶节点,对根节点就是叶节点的情况单独处理,详细见注释。

解决方法

class Solution {
public:
    
    void _findLeaves(TreeNode *super, TreeNode *node, int level, vector<vector<int>>& vec) {
        if (!node) {
            return;
        }
        // 判断是否是叶节点
        if (!node->left && !node->right) {
            // 是叶节点,分别看是父节点的左还是右节点,分别处理
            if (super->left == node) {
                super->left = nullptr;
            } else if (super->right == node) {
                super->right = nullptr;
            }
            vec[level].push_back(node->val);
        } else {
            // 不是叶节点的话,继续递归
            _findLeaves(node, node->left, level, vec);
            _findLeaves(node, node->right, level, vec);
        }
    }
    
    vector<vector<int>> findLeaves(TreeNode* root) {
        vector<vector<int>> vec;
        if (!root) {
            return vec;
        }
        int level = 0;
        while (root->left || root->right) {
            vec.push_back({});
            // 分别对左右子树进行剥离
            _findLeaves(root, root->left, level, vec);
            _findLeaves(root, root->right, level, vec);
            level++;
        }
        vec.push_back({ root->val });
        
        return vec;
    }
};

Thanks for reading.

All the best wishes for you! 💕