366. 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:

          []         

Credits:
Special thanks to @elmirap for adding this problem and creating all test cases.

 

这道题给了我们一个二叉树,让我们返回其每层的叶节点,就像剥洋葱一样,将这个二叉树一层一层剥掉,最后一个剥掉根节点。那么题目中提示说要用DFS来做,思路是这样的,每一个节点从左子节点和右子节点分开走可以得到两个深度,由于成为叶节点的条件是左右子节点都为空,所以我们取左右子节点中较大值加1为当前节点的深度值,知道了深度值就可以将节点值加入到结果res中的正确位置了,求深度的方法我们可以参见 Maximum Depth of Binary Tree 中求最大深度的方法,参见代码如下:

 

解法一:

class Solution {
public:
    vector<vector<int>> findLeaves(TreeNode* root) {
        vector<vector<int>> res;
        helper(root, res);
        return res;
    }
    int helper(TreeNode* root, vector<vector<int>>& res) {
        if (!root) return -1;
        int depth = 1 + max(helper(root->left, res), helper(root->right, res));
        if (depth >= res.size()) res.resize(depth + 1);
        res[depth].push_back(root->val);
        return depth;
    }
};

 

下面这种DFS方法没有用计算深度的方法,而是使用了一层层剥离的方法,思路是遍历二叉树,找到叶节点,将其赋值为NULL,然后加入leaves数组中,这样一层层剥洋葱般的就可以得到最终结果了:

 

解法二:

class Solution {
public:
    vector<vector<int>> findLeaves(TreeNode* root) {
        vector<vector<int>> res;
        while (root) {
            vector<int> leaves;
            root = remove(root, leaves);
            res.push_back(leaves);
        }
        return res;
    }
    TreeNode* remove(TreeNode* node, vector<int>& leaves) {
        if (!node) return NULL;
        if (!node->left && !node->right) {
            leaves.push_back(node->val);
            return NULL;
        }
        node->left = remove(node->left, leaves);
        node->right = remove(node->right, leaves);
        return node;
    }
};

 

还有一种不用建立新的递归函数的方法,就用本身来做递归,我们首先判空,然后对左右子结点分别调用递归函数,这样我们suppose左右子结点的所有叶结点已经按顺序存好到了二维数组left和right中,现在要做的就是把两者合并。但是我们现在并不知道左右子树谁的深度大,我们希望将长度短的二维数组加入到长的里面,那么就来比较下两者的长度,把长度存到结果res中,把短的存入到t中,然后遍历短的,按顺序都加入到结果res里,好在这道题没有强行要求每层的叶结点要按照从左到右的顺序存入。当左右子树的叶结点融合完成了之后,当前结点也要新开一层,直接自己组一层,加入结果res中即可,参见代码如下:

 

解法三:

class Solution {
public:
    vector<vector<int>> findLeaves(TreeNode* root) {
        if (!root) return {};
        vector<vector<int>> left = findLeaves(root->left), right = findLeaves(root->right);
        vector<vector<int>> res = (left.size() >= right.size()) ? left : right;
        vector<vector<int>> t = (left.size() >= right.size()) ? right : left;
        for (int i = 0; i < t.size(); ++i) {
            res[i].insert(res[i].begin(), t[i].begin(), t[i].end());
        }
        res.push_back({root->val});
        return res;
    }
};

 

类似题目:

Maximum Depth of Binary Tree

Minimum Height Trees

 

参考资料:

https://leetcode.com/problems/find-leaves-of-binary-tree/

https://leetcode.com/problems/find-leaves-of-binary-tree/discuss/83773/1-ms-Easy-understand-Java-Solution

https://leetcode.com/problems/find-leaves-of-binary-tree/discuss/191609/10%2B-line-Java-solution-using-recursion

https://leetcode.com/problems/find-leaves-of-binary-tree/discuss/83778/10-lines-simple-Java-solution-using-recursion-with-explanation

 

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation