Binary-Tree-Right-Side-View

第66天。

今天的题目是Binary Tree Right Side View:

Given 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].

挺有趣的题目。

简单的来讲,首先,我们肯定是要让右子树优先,然后还要保证在左子树比右子树高的情况下,它的节点也能被放到要返回的数组中。

要比较高度,我们就需要在遍历的时候带上一个height,然后我们从按右子树优先进行先序遍历,这样就可以保证上面两个条件满足了,那,现在就是要计算什么时候将节点加入数组了。

我们可以发现返回的数组的大小和树的高度是相同的,这样我们就可以通过当前节点的高度来决定是否要将值加入数组,又因为我们遍历的时候已经是右子树优先了,所以第一次遇到这个高度的节点的时候,我们就可以直接将其放入数组中。

1
2
3
4
5
6
7
8
9
10
11
vector<int> rightSideView1(TreeNode* root) {
vector<int> ret;
helper(root,0,ret);
return ret;
}
void helper(TreeNode *root,int height,vector<int> &ret) {
if (root == nullptr) return ;
if (height == ret.size()) ret.push_back(root->val);
helper(root->right,height + 1,ret);
helper(root->left,height+1,ret);
}

然后是dicuss中用层次遍历做的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<Integer> rightSideView(TreeNode root) {
// reverse level traversal
List<Integer> result = new ArrayList();
Queue<TreeNode> queue = new LinkedList();
if (root == null) return result;

queue.offer(root);
while (queue.size() != 0) {
int size = queue.size();
for (int i=0; i<size; i++) {
TreeNode cur = queue.poll();
if (i == 0) result.add(cur.val);
if (cur.right != null) queue.offer(cur.right);
if (cur.left != null) queue.offer(cur.left);
}

}
return result;
}