두 갈래 트리 앞 순서 반복--[비귀속] C 언어 창고 구현

leetcode144 Binary Tree Preorder Traversal

1. 문제 설명

두 갈래 트리를 지정하고 노드 값의 순서를 되돌려줍니다. ---비귀속 실현 사용
[예제]
입력: [1,null, 2,3]
   1
   \
     2
   /
   3
출력: [1,2,3]

2. 문제 풀이 사고방식

비귀속 전차례 반복 사고방식:
step1: 하나의 결점을 훑어보고 (출력하거나 결과 그룹에 저장) [뿌리]에 접근한 다음 창고를 눌러서 왼쪽 트리를 훑어보십시오 [좌]
step2: 왼쪽 트리가 지나가면 창고 꼭대기에서 이 노드를 꺼내서 오른쪽 아이를 가리키며 step1 단계를 계속합니다
step3: 모든 결점에 접근할 때, 즉 마지막으로 접근한 트리 노드가 비어 있고 창고도 비어 있을 때, 알고리즘이 끝납니다

3. 알고리즘 실현

1. 창고 데이터 구조 구축 및 이차 트리 데이터 구조 정의

#include 
#include 
#include 

/** **/
struct TreeNode
{
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
}TreeNode;

/** **/
#define MAXSIZE 10000
#define OVERFLOW 0
#define error -65530

/** **/
typedef struct Sq_stack
{
    struct TreeNode data[MAXSIZE];
    int top;
}Sq_stack;

/** -- **/
void initStack(Sq_stack *S)
{
    S = (Sq_stack*)malloc(sizeof(Sq_stack));
    if(!S)
        exit(OVERFLOW);// 
    S->top = 0; // 0 
}

/** e**/
bool Push(Sq_stack *S, struct TreeNode* e)
{
    /** ： **/
    if( S->top == MAXSIZE-1 )
        return false;
    S->top++;
    S->data[S->top] = *e;
    return true;
}

/** , **/
struct TreeNode* Pop(Sq_stack *S)
{
    /** ： **/
    if(S->top == 0)
        return NULL;
    struct TreeNode* e = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    *e = S->data[S->top];
    S->top--;
    return e;
}

bool isEmptyStack( Sq_stack *S )
{
    return S->top == 0?true:false;
}

2. 전차 역행 비귀속 실현 알고리즘

/****************************************
Author:tmw
date:2018-5-7
****************************************/
/**
*returnSize: 
        --- *result ， *returnSize
**/
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
    if( root == NULL ) return NULL;

    /** **/
    int* result = (int*)malloc(1000*sizeof(int));
    int len=0;

    /** **/
    Sq_stack* stk = (Sq_stack*)malloc(sizeof(Sq_stack));
    initStack(stk);

    while( root || !isEmptyStack(stk) )
    {
        while( root )
        {
            /** ， ， **/
            result[len++] = root->val; /** **/
            Push(stk,root);
            root = root->left; /** **/
        }
        if( !isEmptyStack(stk) )
        {
            root = Pop(stk);
            root = root->right;/** **/
        }
    }
    *returnSize = len;
    return result;
}

4. 실행 결과

leetcode accept
꿈은 있어야지 만일 이루어진다면 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~