513. Find Bottom Left Tree Value

 

Given a binary tree, find the leftmost value in the last row of the tree.

Example 1:

Input:

    2
   / \
  1   3

Output:
1

Example 2: 

Input:

        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7

Output:
7

Note: You may assume the tree (i.e., the given root node) is not NULL.

 

这道题让我们求二叉树的最左下树结点的值,也就是最后一行左数第一个值,那么我首先想的是用先序遍历来做,我们维护一个最大深度和该深度的结点值,由于先序遍历遍历的顺序是根-左-右,所以每一行最左边的结点肯定最先遍历到,那么由于是新一行,那么当前深度肯定比之前的最大深度大,所以我们可以更新最大深度为当前深度,结点值res为当前结点值,这样在遍历到该行其他结点时就不会更新结果res了,参见代码如下:

 

解法一:

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {int max_depth = 1, res = root->val;
        helper(root, 1, max_depth, res);
        return res;
    }
    void helper(TreeNode* node, int depth, int& max_depth, int& res) {
        if (!node) return;
        if (depth > max_depth) {
            max_depth = depth;
            res = node->val;
        }
        helper(node->left, depth + 1, max_depth, res);
        helper(node->right, depth + 1, max_depth, res);
    }
};

 

其实这道题用层序遍历更直接一些,因为层序遍历时遍历完当前行所有结点之后才去下一行,那么我们再遍历每行第一个结点时更新结果res即可,根本不用维护最大深度了,参见代码如下:

 

解法二:

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        int res = 0;
        queue<TreeNode*> q{{root}};
        while (!q.empty()) {
            int n = q.size();
            for (int i = 0; i < n; ++i) {
                TreeNode *t = q.front(); q.pop();
                if (i == 0) res = t->val;
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
        }
        return res;
    }
};

 

我们还可以使用个小trick,使得其更加的简洁,由于一般的层序是从左往右的,那么如果我们反过来,每次从右往左遍历,这样就不用检测每一层的起始位置了,最后一个处理的结点一定是最后一层的最左结点,我们直接返回其结点值即可,参见代码如下:

 

解法三:

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> q{{root}};
        while (!q.empty()) {
            root = q.front(); q.pop();
            if (root->right) q.push(root->right);
            if (root->left) q.push(root->left);
        }
        return root->val;
    }
};

 

参考资料:

https://leetcode.com/problems/find-bottom-left-tree-value/

https://leetcode.com/problems/find-bottom-left-tree-value/discuss/98779/Right-to-Left-BFS-(Python-%2B-Java)

https://leetcode.com/problems/find-bottom-left-tree-value/discuss/98786/verbose-java-solution-binary-tree-level-order-traversal

 

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


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

💰


微信打赏


Venmo 打赏

×

Help us with donation