Code & Func

第66天。

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

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

1
public List<Integer> rightSideView(TreeNode root) {
2
    // reverse level traversal
3
    List<Integer> result = new ArrayList();
4
    Queue<TreeNode> queue = new LinkedList();
5
    if (root == null) return result;
6

7
    queue.offer(root);
8
    while (queue.size() != 0) {
9
        int size = queue.size();
10
        for (int i=0; i<size; i++) {
11
            TreeNode cur = queue.poll();
12
            if (i == 0) result.add(cur.val);
13
            if (cur.right != null) queue.offer(cur.right);
14
            if (cur.left != null) queue.offer(cur.left);
15
        }
4 collapsed lines
16

17
    }
18
    return result;
19
}