[LeetCode] 366. Find Leaves of Binary Tree 找二叉树的叶节点

2021年09月15日 阅读数:1
这篇文章主要向大家介绍[LeetCode] 366. Find Leaves of Binary Tree 找二叉树的叶节点,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

Given a binary tree, find all leaves and then remove those leaves. Then repeat the previous steps until the tree is empty.html

Example:
Given binary tree java

          1
         / \
        2   3
       / \     
      4   5    

Returns [4, 5, 3], [2], [1].node

Explanation:python

1. Remove the leaves [4, 5, 3] from the treeapp

          1
         / 
        2          

2. Remove the leaf [2] from the treepost

          1          

3. Remove the leaf [1] from the treethis

          []         

Returns [4, 5, 3], [2], [1].url

 

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

给一个二叉树,找出它的叶节点而后删除,重复此步骤,直到二叉树为空。htm

The key to solve this problem is converting the problem to be finding the index of the element in the result list. Then this is a typical DFS problem on trees.

Java:

public List<List<Integer>> findLeaves(TreeNode root) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    helper(result, root);
    return result;
}
 
// traverse the tree bottom-up recursively
private int helper(List<List<Integer>> list, TreeNode root){
    if(root==null)
        return -1;
 
    int left = helper(list, root.left);
    int right = helper(list, root.right);
    int curr = Math.max(left, right)+1;
 
    // the first time this code is reached is when curr==0,
    //since the tree is bottom-up processed.
    if(list.size()<=curr){
        list.add(new ArrayList<Integer>());
    }
 
    list.get(curr).add(root.val);
 
    return curr;
} 

Python:

class Solution(object):
    def findLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        def findLeavesHelper(node, result):
            if not node:
                return -1
            level = 1 + max(findLeavesHelper(node.left, result), \
                            findLeavesHelper(node.right, result))
            if len(result) < level + 1:
                result.append([])
            result[level].append(node.val)
            return level

        result = []
        findLeavesHelper(root, result)
        return result

C++:

// Time:  O(n)
// Space: O(h)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> findLeaves(TreeNode* root) {
        vector<vector<int>> result;
        findLeavesHelper(root, &result);
        return result;
    }

private:
    int findLeavesHelper(TreeNode *node, vector<vector<int>> *result) {
        if (node == nullptr) {
            return -1;
        }
        const int level = 1 + max(findLeavesHelper(node->left, result),
                                  findLeavesHelper(node->right, result));
        if (result->size() < level + 1){
            result->emplace_back();
        }
        (*result)[level].emplace_back(node->val);
        return level;
    }
};

   

相似题目:

[LeetCode] 104. Maximum Depth of Binary Tree 二叉树的最大深度

[LeetCode] 310. Minimum Height Trees 最小高度树

[LeetCode] 545. Boundary of Binary Tree 二叉树的边界

 

All LeetCode Questions List 题目汇总