iven a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
For example:
Given the following binary tree,
1
/ \
2 3
\ \
5 4
You should return [1, 3, 4].
My Solution
代码的run time是3ms (10.90%),时间复杂度,空间复杂度。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> rightSideView(TreeNode root) {
LinkedList<Integer> li = new LinkedList<>();
LinkedList<TreeNode> lt = new LinkedList<>();
if (root == null) {
return li;
}
lt.add(root);
int number = 1;
while (!lt.isEmpty()) {
TreeNode element = lt.peek();
li.add(element.val);
int nextNumber = 0;
for (; number > 0; --number) {
element = lt.poll();
nextNumber += addChild(lt, element);
}
number = nextNumber;
}
return li;
}
private int addChild(LinkedList<TreeNode> lt, TreeNode element) {
int number = 0;
if (element.right != null) {
lt.add(element.right);
++number;
}
if (element.left != null) {
lt.add(element.left);
++number;
}
return number;
}
}
Description
iven a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
For example: Given the following binary tree,
You should return
[1, 3, 4]
.My Solution
代码的run time是3ms (10.90%),时间复杂度,空间复杂度。
Analysis
这个就是一个简单的BFS,没啥好说的。