LeetCode //C - 199. Binary Tree Right Side View-Toy模板网

这篇具有很好参考价值的文章主要介绍了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:

LeetCode //C - 199. Binary Tree Right Side View,LeetCode,leetcode,c语言,算法

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.文章来源地址https://www.toymoban.com/news/detail-809647.html

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;
}