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 | vector<int> rightSideView1(TreeNode* root) { |
然后是dicuss
中用层次遍历做的:
1 | public List<Integer> rightSideView(TreeNode root) { |