199. Binary Tree Right Side View
1. Description
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.
2. Example
Example 1:
Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
3. Solutions
My Accepted Solution
n is the number of nodes in i_root
Time complexity: O(n)
Space complexity: O(n)
class Solution
{
public:
// vector<int> rightSideView(TreeNode* root)
vector<int> rightSideView(TreeNode *i_root)
{
if(!i_root) return vector<int>{};
vector<int> result{i_root->val};
queue<const TreeNode *> currentLevelNodes{{i_root}};
queue<const TreeNode *> nextLevelNodes;
while(!currentLevelNodes.empty() || !nextLevelNodes.empty())
{
if(currentLevelNodes.empty())
{
swap(currentLevelNodes, nextLevelNodes);
result.push_back(currentLevelNodes.back()->val);
}
else
{
auto node = currentLevelNodes.front();
currentLevelNodes.pop();
if(node->left) nextLevelNodes.push(node->left);
if(node->right) nextLevelNodes.push(node->right);
}
}
return result;
}
};
3.1 Depth-first Search
n is the number of nodes in i_root
Time complexity: O(n)
Space complexity: O(n)
// the question if find the most right node, so we try to iterate the right subtree
class Solution
{
public:
// vector<int> rightSideView(TreeNode* root)
vector<int> rightSideView(TreeNode *i_root)
{
if(!i_root) return vector<int>{};
unordered_map<int, int> mostRightValueAtDepth;
int maxDepth = -1;
stack<TreeNode *> parentNodes{{i_root}};
stack<int> depthStack{{0}}; // depth stack let nodes know their depth
while(!parentNodes.empty())
{
auto node = parentNodes.top();
parentNodes.pop();
int depth = depthStack.top();
depthStack.pop();
maxDepth = max(maxDepth, depth);
if(mostRightValueAtDepth.find(depth) == mostRightValueAtDepth.end())
{
mostRightValueAtDepth[depth] = node->val;
}
// because parentNodes is a stack, if the push order is left right
// the pop order will be right left, so we try best to iterate the most right node
if(node->left)
{
parentNodes.push(node->left);
depthStack.push(depth + 1);
}
if(node->right)
{
parentNodes.push(node->right);
depthStack.push(depth + 1);
}
}
vector<int> result(maxDepth + 1);
for (int depth = 0; depth <= maxDepth; depth++)
{
result[depth] = mostRightValueAtDepth[depth];
}
return result;
}
};