LeetCode //C - 199. Binary Tree Right Side View

199. Binary Tree Right Side View

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

From: LeetCode
Link: 199. Binary Tree Right Side View

Solution:

Ideas：

The rightSideView function uses a depth-first search strategy to traverse the tree and record the last value encountered at each depth. This assumes that the tree is being traversed such that the rightmost node at each depth will be the node seen from the right side view. The function then returns an array of these values.

Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

int* rightSideView(struct TreeNode* root, int* returnSize) {
   
    // If the tree is empty
    if (root == NULL) {
   
        *returnSize = 0;
        return NULL;
    }

    int depth = 0;
    int capacity = 8;
    int* rightValues = (int*)malloc(capacity * sizeof(int));
    struct TreeNode** stack = (struct TreeNode**)malloc(capacity * sizeof(struct TreeNode*));
    int* depths = (int*)malloc(capacity * sizeof(int));
    
    if (!rightValues || !stack || !depths) {
   
        // Handle allocation failure if needed
    }

    int stackSize = 0;
    stack[stackSize] = root;
    depths[stackSize++] = 1;

    while (stackSize > 0) {
   
        struct TreeNode* node = stack[--stackSize];
        int currentDepth = depths[stackSize];

        if (currentDepth > depth) {
   
            depth = currentDepth;
            if (depth > capacity) {
   
                capacity *= 2;
                rightValues = (int*)realloc(rightValues, capacity * sizeof(int));
                stack = (struct TreeNode**)realloc(stack, capacity * sizeof(struct TreeNode*));
                depths = (int*)realloc(depths, capacity * sizeof(int));
                
                if (!rightValues || !stack || !depths) {
   
                    // Handle allocation failure if needed
                }
            }
            rightValues[depth - 1] = node->val;
        }

        if (node->left) {
   
            stack[stackSize] = node->left;
            depths[stackSize++] = currentDepth + 1;
        }
        
        if (node->right) {
   
            stack[stackSize] = node->right;
            depths[stackSize++] = currentDepth + 1;
        }
    }

    free(stack);
    free(depths);

    *returnSize = depth;
    return rightValues;
}