---

---

剑指 Offer II 045. 二叉树最底层最左边的值：

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

样例 1：

输入: 
	root = [2,1,3]
	
输出: 
	1
1
2
3
4
5

样例 2：

输入: 
	[1,2,3,4,null,5,6,null,null,7]
	
输出: 
	7
1
2
3
4
5

提示：

• 二叉树的节点个数的范围是 [1,10⁴]
• -2³¹ <= Node.val <= 2³¹ - 1

---

分析

• 面对这道算法题目，二当家的陷入了沉思。
• 遍历二叉树是必然的，关键怎么找到目标节点，可以分成两步。
• 第一步找到最底层：可以按照层序遍历二叉树，最终遍历的就是最底层。
• 第二步找到最左侧节点：存储一层当中的第一个节点值，遍历到最后，存储的结果就是答案；也可以从右向左做层序遍历，那么最后一个遍历的节点就目标节点。

---

题解

rust

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option>>,
//   pub right: Option>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn find_bottom_left_value(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut ans = 0;

        use std::collections::VecDeque;
        let mut q = VecDeque::new();
        q.push_back(root);
        while !q.is_empty() {
            let mut size = q.len();
            (0..size).for_each(|_| {
                if let Some(n) = q.pop_front().flatten() {
                    let n = n.borrow();
                    q.push_back(n.right.clone());
                    q.push_back(n.left.clone());
                    ans = n.val;
                }
            });
        }

        ans
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

---

go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findBottomLeftValue(root *TreeNode) int {
    ans := 0

	var q []*TreeNode
	q = append(q, root)
	for len(q) > 0 {
		ans = q[0].Val
		size := len(q)
		for i := 0; i < size; i++ {
			node := q[i]
			if node.Left != nil {
				q = append(q, node.Left)
			}
			if node.Right != nil {
				q = append(q, node.Right)
			}
		}
		q = q[size:]
	}

	return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

---

typescript

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function findBottomLeftValue(root: TreeNode | null): number {
    let ans = 0;

	const q = new Array();
	q.push(root);
	while (q.length > 0) {
		ans = q[0].val;
		let size = q.length;
		while (--size >= 0) {
			const node = q.shift();
			if (node.left) {
				q.push(node.left);
			}
			if (node.right) {
				q.push(node.right);
			}
		}
	}


	return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

---

python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findBottomLeftValue(self, root: TreeNode) -> int:
        ans = 0
        q = deque()
        q.append(root)
        while len(q) > 0:
            ans = q[0].val
            size = len(q)
            for _ in range(size):
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        return ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

---

c

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


int findBottomLeftValue(struct TreeNode* root){
    int ans = 0;
    struct TreeNode *q[10000];
    int q_index = 0;
    int q_size = 0;
    q[q_size++] = root;
    while (q_index < q_size) {
        ans = q[q_index]->val;
        int size = q_size - q_index;
        while (--size >= 0) {
            struct TreeNode *node = q[q_index++];
            if (node->left) {
                q[q_size++] = node->left;
            }
            if (node->right) {
                q[q_size++] = node->right;
            }
        }
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

---

c++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        int ans = 0;
        queue<TreeNode *> q;
        q.push(root);
        while (q.size() > 0) {
            ans = q.front()->val;
            int size = q.size();
            while (--size >= 0) {
                TreeNode *node = q.front();
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
                q.pop();
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

---

java

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

---

原题传送门：https://leetcode.cn/problems/LwUNpT/

---

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~

---