Given the root of 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.
Example 1:
Input: root = [1,2,3,null,5,null,4] Output: [1,3,4]
Example 2:
Input: root = [1,null,3] Output: [1,3]
Example 3:
Input: root = [] Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Solution: Pre-order traversal
By using pre-order traversal, the right most node will be the last one to visit in each level.
Time complexity: O(n)
Space complexity: O(|height|)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua class Solution { public: vector<int> rightSideView(TreeNode* root) { vector<int> ans; function<void(TreeNode*, int)> dfs = [&](TreeNode* root, int d) { if (!root) return; if (ans.size() < d + 1) ans.push_back(0); ans[d] = root->val; dfs(root->left, d + 1); dfs(root->right, d + 1); }; dfs(root, 0); return ans; } }; |