PTA 03-树3 Tree Traversals Again

Question

在Dev C++里输出答案正确，但过不了PTA测试里的sample测试，显示答案错误DEV C++jie'guo

代码如下

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct stack* Ptrs;
struct BinTree{
    int data;
    int left;
    int right;
};
struct stack{
    int s_data;
    Ptrs next;
};
void push(int data,Ptrs s)
{
    Ptrs tmp;
    tmp=(Ptrs)malloc(sizeof(struct stack));
    tmp->s_data=data;
    if(s->next==NULL)
    {
        s->next=tmp;
        tmp->next=NULL;
    } 
    else
    {
        tmp->next=s->next;
        s->next=tmp;
    }
}
int pop(Ptrs s)
{
    int top;
    Ptrs tmp;
    tmp=s->next;
    top=tmp->s_data;
    s->next=tmp->next;
    free(tmp);
    return top;
}
int top(Ptrs s)
{
    if(s->next==NULL)
    return 0;
    else
    return(s->next->s_data);

}
int Isempty(Ptrs s)
{
    if(s->next==NULL)
    return 0;
    else
    return 1;
}
void plantTree(int N,struct BinTree T[])
{
    char op[5];
    int data;
    Ptrs stack;
    stack=(Ptrs)malloc(sizeof(struct stack));
    stack->next=NULL;
    int k=0;
    int pre_top;
    int flag=0;
    for(int i=0;i<2*N;i++)
    {
        //输入部分 
        scanf("%s",op);
        if(strcmp(op,"Push")==0)
        {
            if(i==2*N-1)
            scanf(" %d",&data);
            else
            scanf(" %d\n",&data);
            if(flag==0)
            pre_top=top(stack);
            push(data,stack);
            T[k].data=data;
            k++;
            if(pre_top!=0)
          {
            if(T[pre_top-1].left==0)
            T[pre_top-1].left=data;
            else
            T[pre_top-1].right=data;
          }
            flag=0;
        }
        else
        {
            if(i==2*N-1);
            else
            scanf("\n");
            pre_top=pop(stack);
            flag=1;//
        }   
    }//plant tree successfully

}

int SearchFather(int child,int N,struct BinTree T[])
{

    for(int i=0;i<N;i++)
    {
        if(T[i].left==child||T[i].right==child)
        return(T[i].data);
    }
    return 0;//root
}
int LeftLeaf(int left,int root,struct BinTree T[],Ptrs stack)//找到左叶，并一直push father和右兄弟；若没有左叶，则不执行push 
{

    while(left!=0)
    {
        if(T[root].data!=top(stack))
        push(T[root].data,stack);
        if(T[root].right!=0)
        push(T[root].right,stack);

        root=left-1;//一直向左的终点 数组序号 
        left=T[root].left;
    }
    if(T[root].data!=top(stack))
    push(T[root].data,stack);

 } 
void postOrderTraversal(int N,struct BinTree T[])
{
    Ptrs stack;
    stack=(Ptrs)malloc(sizeof(struct stack));
    stack->next=NULL;

    int left,root;
     int flag=0;
    root=0;//root
    left=T[root].left;
    //push(T[root].data,stack);
    LeftLeaf(left,root,T,stack); 
    //找到左叶，并push

    while(Isempty(stack)!=0)//栈不空时 
    {
        int _pop;
        _pop=pop(stack);
        if(flag==1)
        printf(" ");
        printf("%d",_pop);//输出 
        flag=1;
        int father=SearchFather(_pop,N,T); 
        if(top(stack)!=father)//还有右兄弟分支需遍历 ，若相等说明已经遍历过右边 
      {
        root=top(stack)-1;
        left=T[root].left;
        LeftLeaf(left,root,T,stack);//find leftleaf

      }
    }

 } 

int main()
{
    int N;
    scanf("%d\n",&N);
    struct BinTree T[N]={0};
    plantTree(N,T);
    postOrderTraversal(N,T);
    return 0;
}

Answer 1

以下回答参考 皆我百晓生、券券喵儿 等免费微信小程序相关内容作答，并由本人整理回复。

#include <stdio.h>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
class Solution {
public:
    void dfs(TreeNode* root, vector<int>& ans) {
        if (root == NULL) {
            return;
        }
        dfs(root->left, ans);
        dfs(root->right, ans);
        ans.push_back(root->val);
    }

    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == NULL && q == NULL) {
            return true;
        }
        if (p == NULL || q == NULL) {
            return false;
        }
        return p->val == q->val &&
               isSameTree(p->left, q->left) &&
               isSameTree(p->right, q->right);
    }
};

TreeNode* buildTree(vector<int> &inorder, vector<int> &postorder) {
    unordered_map<int, int> inorderIndexMap;
    for (int i = 0; i < inorder.size(); ++i) {
        inorderIndexMap[inorder[i]] = i;
    }
    return solve(inorderIndexMap, postorder, 0, inorder.size() - 1);
}

TreeNode* solve(unordered_map<int, int> &inorderIndexMap, vector<int> &postorder, int inLeft, int inRight) {
    if (inLeft > inRight) {
        return nullptr;
    }
    int rootVal = postorder[postorder.size() - 1];
    TreeNode* root = new TreeNode(rootVal);
    int inRootIndex = inorderIndexMap[rootVal];
    int leftPostSize = inRootIndex - inLeft;
    root->left = solve(inorderIndexMap, postorder, inLeft, inRootIndex - 1);
    root->right = solve(inorderIndexMap, postorder, inRootIndex + 1, inRight);
    return root;
}