"反黑话"
要说互联网有什么破圈的"糟粕"之处，那"互联网黑话"必然是其中之一（甚至可能是榜首）。
如果我问，哪家大厂对"黑话"最中意？
可能不少人脑袋一闪而过，会是 A 姓大厂，毕竟"AL 味"这词深入人心。
那如果我问，哪家大厂对"黑话"最反感呢？
可能就比较少人脑里会有答案。
但字节必然会是实际中的一员，多年以前，字节创始人张一鸣就曾公开表示过要抵制"黑话"，甚至在某年的年会 PPT 中，专门留了一页来批判该风气。
老板都发话了，字节的行政部门，自然也是把思想贯彻到底，甚至可以说是"玩出花样"。
去年年底，字节就在某次内购活动中，随机赠送了"黑话帆布袋"，当时不少员工就冲着帆布袋这个赠品去参与购买 🤣🤣🤣
今年年底，字节则直接把"反黑话"宣传标语直接印在 WC 中。
主打就是「曝光度最大化」+「不留情面」。
该说不说，字节这一举措还是挺加分的，如果一个公司只是形式上的"扁平化"，这样的活动是很难实际推行的，毕竟哪家公司还没有几个（从 A 姓公司过来的）爱讲黑话的高管呢
对此，你怎么看？
...
回归主题。
周末，来一道简单算法题。
题目描述
平台：LeetCode
题号：513
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3]
输出: 1
示例 2:
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
提示:
二叉树的节点个数的范围是
BFS
使用 BFS 进行「层序遍历」，每次用当前层的首个节点来更新 ans，当 BFS 结束后，ans 存储的是最后一层最靠左的节点。
Java 代码：
class Solution {
public int findBottomLeftValue(TreeNode root) {
Deque<TreeNode> d = new ArrayDeque<>();
d.addLast(root);
int ans = 0;
while (!d.isEmpty()) {
int sz = d.size();
ans = d.peek().val;
while (sz-- > 0) {
TreeNode poll = d.pollFirst();
if (poll.left != null) d.addLast(poll.left);
if (poll.right != null) d.addLast(poll.right);
}
}
return ans;
}
}
C++ 代码：
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
deque<TreeNode*> d;
d.push_back(root);
int ans = 0;
while (!d.empty()) {
int sz = d.size();
ans = d.front()->val;
while (sz-- > 0) {
TreeNode* poll = d.front();
d.pop_front();
if (poll->left != nullptr) d.push_back(poll->left);
if (poll->right != nullptr) d.push_back(poll->right);
}
}
return ans;
}
};
Python 代码：
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
d = deque([root])
ans = 0
while d:
sz = len(d)
ans = d[0].val
while sz > 0:
poll = d.popleft()
if poll.left:
d.append(poll.left)
if poll.right:
d.append(poll.right)
sz -= 1
return ans
TypeScript 代码：
function findBottomLeftValue(root: TreeNode | null): number {
const d = [root];
let ans = 0;
while (d.length > 0) {
const sz = d.length;
ans = d[0].val;
for (let i = 0; i < sz; i++) {
const poll = d.shift()!;
if (poll.left) d.push(poll.left);
if (poll.right) d.push(poll.right);
}
}
return ans;
};
时间复杂度： 空间复杂度：最坏情况下所有节点都在同一层，复杂度为
DFS
同理，可以使用 DFS 进行树的遍历，每次优先 DFS 当前节点的左子树，每次第一次搜索到当前深度 depth 时，必然是当前深度的最左节点，此时用当前节点值来更新 ans。
Java 代码：
class Solution {
int max, ans;
public int findBottomLeftValue(TreeNode root) {
dfs(root, 1);
return ans;
}
void dfs(TreeNode root, int depth) {
if (root == null) return ;
if (depth > max) {
max = depth; ans = root.val;
}
dfs(root.left, depth + 1);
dfs(root.right, depth + 1);
}
}
C++ 代码：
class Solution {
public:
int maxv = 0, ans = 0;
int findBottomLeftValue(TreeNode* root) {
dfs(root, 1);
return ans;
}
void dfs(TreeNode* root, int depth) {
if (!root) return;
if (depth > maxv) {
maxv = depth; ans = root->val;
}
dfs(root->left, depth + 1);
dfs(root->right, depth + 1);
}
};
Python 代码：
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
self.maxv, self.ans = 0, 0
self.dfs(root, 1)
return self.ans
def dfs(self, root: TreeNode, depth: int) -> None:
if not root:
return
if depth > self.maxv:
self.maxv = depth
self.ans = root.val
self.dfs(root.left, depth + 1)
self.dfs(root.right, depth + 1)
TypeScript 代码：
let max, ans;
function dfs(root: TreeNode | null, depth: number): void {
if (!root) return;
if (depth > max) {
max = depth;
ans = root.val;
}
dfs(root.left, depth + 1);
dfs(root.right, depth + 1);
}
function findBottomLeftValue(root: TreeNode | null): number {
max = 0; ans = 0;
dfs(root, 1);
return ans;
};
时间复杂度： 空间复杂度：最坏情况下退化成链，递归深度为 。复杂度为
最后
巨划算的 LeetCode 会员优惠通道目前仍可用 ~
使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier，年度会员 有效期额外增加两个月，季度会员 有效期额外增加两周，更有超大额专属 🧧 和实物 🎁 福利每月发放。
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。
