[LeetCode] 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.

Example:
Given binary tree 

1
/ \
2   3
/ \     
4   5    

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

Explanation:

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

1
/ 
2          

2. Remove the leaf [2] from the tree

1          

3. Remove the leaf [1] from the tree

[]         

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

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;
    }
};

本文转自博客园Grandyang的博客,原文链接:找二叉树的叶节点[LeetCode] Find Leaves of Binary Tree ,如需转载请自行联系原博主。

相关文章
|
17天前
【LeetCode 31】104.二叉树的最大深度
【LeetCode 31】104.二叉树的最大深度
15 2
|
17天前
【LeetCode 29】226.反转二叉树
【LeetCode 29】226.反转二叉树
15 2
|
17天前
【LeetCode 28】102.二叉树的层序遍历
【LeetCode 28】102.二叉树的层序遍历
11 2
|
17天前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
10 0
|
17天前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
9 0
|
17天前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
10 0
|
17天前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
10 0
|
17天前
【LeetCode 32】111.二叉树的最小深度
【LeetCode 32】111.二叉树的最小深度
11 0
|
3月前
|
存储 算法
二叉树进阶-学会层序遍历助你一次刷完leetcode10道题
文章深入探讨了二叉树的层序遍历方法,并展示了如何通过队列实现层序遍历的算法逻辑,同时指出掌握层序遍历技巧可以帮助解决LeetCode上的多道相关题目。
二叉树进阶-学会层序遍历助你一次刷完leetcode10道题
|
3月前
|
算法 Java
LeetCode第94题二叉树的中序遍历
文章介绍了LeetCode第94题"二叉树的中序遍历"的解法,使用递归实现了中序遍历的过程,遵循了"左根右"的遍历顺序,并提供了清晰的Java代码实现。
LeetCode第94题二叉树的中序遍历