- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
题目地址:https://leetcode.com/problems/find-bottom-left-tree-value/#/descriptionopen in new window
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算法。广度优先搜索,但是搜索的顺序是有要求的,因为题目要最底层的叶子节点的最左边的叶子,那么进入队列的顺序就是先右节点再左节点,这样能把每层的节点都能从右到左过一遍,那么用一个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;
}
}
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
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]
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
使用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];
}
};
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
使用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)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
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);
}
};
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
DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有
本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发
例如,我有一个父类Author: class Author { String name static hasMany = [ fiction: Book,
代码如下: dojo.query(subNav.navClass).forEach(function(node, index, arr){ if(dojo.style(node, 'd
我有一个带有 Id 和姓名的学生表和一个带有 Id 和 friend Id 的 Friends 表。我想加入这两个表并找到学生的 friend 。 例如,Ashley 的 friend 是 Saman
我通过互联网浏览,但仍未找到问题的答案。应该很容易: class Parent { String name Child child } 当我有一个 child 对象时,如何获得它的 paren
我正在尝试创建一个以 Firebase 作为我的后端的社交应用。现在我正面临如何(在哪里?)找到 friend 功能的问题。 我有每个用户的邮件地址。 我可以访问用户的电话也预订。 在传统的后端中,我
我主要想澄清以下几点: 1。有人告诉我,在 iOS 5 及以下版本中,如果您使用 Game Center 设置多人游戏,则“查找 Facebook 好友”(如与好友争夺战)的功能不是内置的,因此您需要
关于redis docker镜像ENTRYPOINT脚本 docker-entrypoint.sh : #!/bin/sh set -e # first arg is `-f` or `--some-
我是一名优秀的程序员,十分优秀!