513. Find Bottom Left Tree Value 找树左下角的值

作者： 负雪明烛 id： fuxuemingzhu 个人博客： http://fuxuemingzhu.cn/

---

@TOC

题目地址：https://leetcode.com/problems/find-bottom-left-tree-value/#/description

题目描述

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.

题目大意

求一个二叉树最下面一层的最左边节点。

解题方法

BFS

这就是所谓的BFS算法。广度优先搜索，但是搜索的顺序是有要求的，因为题目要最底层的叶子节点的最左边的叶子，那么进入队列的顺序就是先右节点再左节点，这样能把每层的节点都能从右到左过一遍，那么用一个int保存最后的节点值就可以了。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int findBottomLeftValue(TreeNode root) {
        int ans = 0;
        Queue<TreeNode> tree = new LinkedList<TreeNode>();
        tree.offer(root);
        while(!tree.isEmpty()){
            TreeNode temp = tree.poll();
            if(temp.right != null){
                tree.offer(temp.right);
            }
            if(temp.left != null){
                tree.offer(temp.left);
            }
            ans = temp.val;
        }
        return ans;
    }
}

Python做法是用层次遍历，用的是双向队列，所以注意append和popleft。代码如下：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def findBottomLeftValue(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        q = collections.deque()
        q.append(root)
        res = []
        while q:ruxai
            size = len(q)
            level = []
            for i in range(size):
                node = q.popleft()
                if not node: continue
                level.append(node.val)
                q.append(node.left)
                q.append(node.right)
            if level:
                res.append(level)
        return res[-1][0]

使用C++用的是BFS版本的层次遍历，代码如下：

/**
 * 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:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        vector<vector<int>> res;
        while (!q.empty()) {
            int size = q.size();
            vector<int> level;
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front(); q.pop();
                if (!node) continue;
                level.push_back(node->val);
                q.push(node->left);
                q.push(node->right);
            }
            if (!level.empty()) {
                res.push_back(level);
            }
        }
        return res[res.size() - 1][0];
    }
};

DFS

使用DFS很简单了，直接把每一层的元素放到list里面，然后取出最后层的第一个节点即可。至于子树的遍历顺序，需要保证先遍历左子树再遍历右子树，这样才能把最下面一层的最左边节点放到最左侧，至于根节点的值在哪个位置进行append是不重要的。

python代码如下：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def findBottomLeftValue(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        res = []
        self.dfs(root, res, 0)
        return res[-1][0]
    
    def dfs(self, root, res, level):
        if not root: return
        if level == len(res): res.append([])
        res[level].append(root.val)
        self.dfs(root.left, res, level + 1)
        self.dfs(root.right, res, level + 1)

C++代码需要注意的是，我们应该对res传引用进来，否则不能对外部变量进行更改。

/**
 * 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:
    int findBottomLeftValue(TreeNode* root) {
        dfs(root, res, 0);
        return res[res.size() - 1][0];
    }
private:
    vector<vector<int>> res;
    void dfs(TreeNode* root, vector<vector<int>>& res, int level) {
        if (!root) return;
        if (level == res.size()) res.push_back({});
        res[level].push_back(root->val);
        dfs(root->left, res, level + 1);
        dfs(root->right, res, level + 1);
    }
};

Date

2017 年 4 月 13 日