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

找树左下角的值。

题意是给一个二叉树，请return最底层，最靠左边节点的值。这个题可以用BFS和DFS做。两种做法的时间和空间复杂度都是O(n)。

首先BFS比较直观，只要按层序遍历的做法一层层把node塞进queue。当遍历到最底层的时候，输出第一个塞进去的节点值即可。注意每层节点在塞入queue的时候应该是先塞右孩子再塞左孩子，原因是BFS的解法不看当前遍历到了第几层，只能通过这种方式才能保证最底层最靠左的叶子节点是最后被塞入queue的。如果按照第一个例子跑一遍，结果就是2 - 3 - 1而不是2 - 1 - 3.

JavaScript实现

 1 /**
 2  * @param {TreeNode} root
 3  * @return {number}
 4  */
 5 var findBottomLeftValue = function (root) {
 6     // corner case
 7     if (root === null) {
 8         return -1;
 9     }
10 
11     // normal case
12     let res = null;
13     let queue = [root];
14     while (queue.length > 0) {
15         let cur = queue.shift();
16         res = cur.val;
17         if (cur.right) {
18             queue.push(cur.right);
19         }
20         if (cur.left) {
21             queue.push(cur.left);
22         }
23     }
24     return res;
25 };

Java实现

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode() {}
 8  *     TreeNode(int val) { this.val = val; }
 9  *     TreeNode(int val, TreeNode left, TreeNode right) {
10  *         this.val = val;
11  *         this.left = left;
12  *         this.right = right;
13  *     }
14  * }
15  */
16 class Solution {
17     public int findBottomLeftValue(TreeNode root) {
18         // corner case
19         if (root == null) {
20             return -1;
21         }
22 
23         // normal case
24         int res = 0;
25         Queue<TreeNode> queue = new LinkedList<>();
26         queue.offer(root);
27         while (!queue.isEmpty()) {
28             TreeNode cur = queue.poll();
29             res = cur.val;
30             if (cur.right != null) {
31                 queue.offer(cur.right);
32             }
33             if (cur.left != null) {
34                 queue.offer(cur.left);
35             }
36         }
37         return res;
38     }
39 }

用DFS做的思路就稍微复杂一些。DFS的做法会用到先序遍历，会先判断左子树。很显然如果有左子树，左子树的深度会是当前深度+1；但是遍历到右子树的时候，深度不会变化。

JavaScript实现

 1 /**
 2  * @param {TreeNode} root
 3  * @return {number}
 4  */
 5 var findBottomLeftValue = function(root) {
 6     let highestLevel = -1;
 7     let leftMost = null;
 8     const helper = (node, level) => {
 9         if (!node) return;
10         if (level > highestLevel) {
11             highestLevel = level;
12             leftMost = node.val;
13         }
14         helper(node.left, level + 1);
15         helper(node.right, level + 1);
16     };
17     helper(root, 0);
18     return leftMost;
19 };

Java实现

 1 /**
 2  * Definition for a binary tree node. public class TreeNode { int val; TreeNode
 3  * left; TreeNode right; TreeNode(int x) { val = x; } }
 4  */
 5 class Solution {
 6     int res = 0;
 7     int height = 0;
 8 
 9     public int findBottomLeftValue(TreeNode root) {
10         if (root == null)
11             return -1;
12         helper(root, 1);
13         return res;
14     }
15 
16     public void helper(TreeNode root, int depth) {
17         if (root == null)
18             return;
19         if (height < depth) {
20             res = root.val;
21             height = dpeth;
22         }
23         helper(root.left, depth + 1);
24         helper(root.right, depth + 1);
25     }
26 }

LeetCode 题目总结