题目大意：给你一棵树，返回左下角（最后一行最左面）的节点的值。
https://leetcode.com/problems/find-bottom-left-tree-value/description/
Problem:
Given a binary tree, find the leftmost value in the last row of the tree.
Example 1:
|
1 2 3 4 5 6 7 8 |
Input: 2 / \ 1 3 Output: 1 |
Example 2:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
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.
Solution 1: Inorder traversal with depth info
The first node visited in the deepest row is the answer.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua // Running time: 12 ms class Solution { public: int findBottomLeftValue(TreeNode* root) { int max_row = -1; int ans; dfs(root, 0, max_row, ans); return ans; } private: void inorder(TreeNode* root, int row, int& max_row, int& ans) { if (root == nullptr) return; inorder(root->left, row + 1, max_row, ans); if (row > max_row) { ans = root->val; max_row = row; } inorder(root->right, row + 1, max_row, ans); } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
""" Author: Huahua Running time: 92 ms """ class Solution: def inorder(self, root, row): if not root: return self.inorder(root.left, row + 1) if row > self.max_row: self.max_row, self.ans = row, root.val self.inorder(root.right, row + 1) def findBottomLeftValue(self, root): self.ans, self.max_row = 0, -1 self.inorder(root, 0) return self.ans |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment