[leetcode]Find Bottom Left Tree Value

Find Bottom Left Tree Value 寻找最底层最右边的叶

原题&翻译

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

给出二叉树,在最后一行寻找最左边的值。

例子 1:

输入:

    2
   / \
  1   3

输出:
1

例子 2:

输入:

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

输出:
7

注意: 您可以认定给定的树不为空。


解题思路

解法一

DFS,就是看心情计算。

class Solution {
public:
    int result = 0;
    int lev = -1;
    int findBottomLeftValue(TreeNode* root) {
        if(!root->left && !root->right) return root->val;
        return find(root, 0);
    }
    int find(TreeNode *root, int level){
        if(!root) return result;
        find(root->left, level+1);
        if(level > lev){
            result = root->val;
            lev = level;
        }
        find(root->right, level+1);
        return result;
    }

};

解法二

搬运过来的 6 ms 的答案,说实话,看不懂,但是大致思路应该是跟上面一样的。

static int x = []() { std::ios::sync_with_stdio(false); cin.tie(NULL); return 0; }();
class Solution {
    void fblv(TreeNode* root, int height, int &maxHeight, int&value) const {
        if(root) {
            if(height > maxHeight) { maxHeight = height; value = root->val; }
            fblv(root->left, height + 1, maxHeight, value);
            fblv(root->right, height + 1, maxHeight, value);
        }
    };
public:
    int findBottomLeftValue(TreeNode* root) const {
        int maxHeight = -1, value = 0;
        fblv(root, 0, maxHeight, value);
        return value;
    };
};

解法三

BFS

class Solution {
public:
    int findLeftMostNode(TreeNode* root) {
        queue<TreeNode*> q;
        queue<int> level;

        q.push(root);
        level.push(0);

        int m=0;
        while(q.size()){
            TreeNode *r = q.front(); q.pop();
            int l = level.front(); level.pop();
            if(r->left) {
                q.push(r->left);
                level.push(l+1);
            }
            if(r->right){
                q.push(r->right);
                level.push(l+1);
            }
            if(l > m){
                m = l;
                root = r;
            }
        }
        return root->val;
    }
};