二叉樹後序周遊--【非遞歸】C語言棧實作

leetcode145 Binary Tree Postorder Traversal

一、問題描述

給定一個二叉樹，傳回它的節點值的後序周遊。---使用非遞歸實作

二、解題思路

非遞歸後序周遊 --- 左右根

對于一個節點而言，要實作通路順序為左兒子-右兒子-根節點，可以利用後進先出的棧，在節點不為空的前提下，依次将根，右，左壓棧。故需要按照根-右-左的順序周遊樹，而先序周遊的順序是根-左-右，故隻需将先序周遊的左右調換并把通路方式列印改為壓入另一個棧即可。最後一起列印棧中的元素

step1:将目前結點同時入臨時棧和結果棧【根】，并周遊右子樹----【右】

step2:當右子樹周遊結束後，彈出臨時棧棧頂結點，并周遊其左子樹----【左】，繼續step1步驟

step3:當所有結點都通路完，即最後通路的樹節點為空且臨時棧也為空時，主算法結束，依次pop出結果棧結點

參考連結：https://www.cnblogs.com/llhthinker/p/4747962.html

三、算法實作

1、棧資料結建構立及二叉樹資料結構定義

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

/**二叉樹資料結構定義**/
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* postorderTraversal(struct TreeNode* root, int* returnSize)
{
    if( root == NULL ) return NULL;

    /**自定義結果數組并初始化**/
    int* result = (int*)malloc(1000*sizeof(int));
    int len = 0;

    /**定義棧并初始化**/
    Sq_stack* stk_result = (Sq_stack*)malloc(sizeof(Sq_stack));
    initStack(stk_result);
    Sq_stack* temp_stk = (Sq_stack*)malloc(sizeof(Sq_stack));
    initStack(temp_stk);

    while( root || !isEmptyStack(temp_stk) )
    {
        /**将目前結點同時入臨時棧和結果棧【根】，并周遊右子樹----【右】**/
        while( root )
        {
            Push(temp_stk,root);
            Push(stk_result,root);
            root = root->right;
        }
        /**當右子樹周遊結束後，彈出臨時棧棧頂結點，并周遊其左子樹----【左】，繼續while**/
        if( !isEmptyStack(temp_stk) )
        {
            root = Pop(temp_stk);
            root = root->left;
        }
    }
    /**
        當所有結點都通路完，即最後通路的樹節點為空且臨時棧也為空時，
        主算法結束，依次pop出結果棧結點
    **/
    struct TreeNode* e = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    while( !isEmptyStack(stk_result) )
    {
        e = Pop(stk_result);
        result[len++] = e->val;
    }
    free(e);
    *returnSize = len;
    return result;
}
           

四、執行結果

leetcode accept

夢想還是要有的，萬一實作了呢~~~ヾ(◍°∇°◍)ﾉﾞ~~~