JD 1385：重建二叉树

本文主要是介绍JD 1385：重建二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

OJ题目：click here~~

题目分析:给前序遍历序列和中序遍历序列，重构二叉树并输出后序遍历序列

剑指offer 面试题6

AC_CODE

int pre[1008] , in[1008] ;
struct Node{int x ;Node *left ;Node *right ;
};bool buildsubtree(Node*& root , int* spre , int* epre , int* sin ,int* ein){int rootV = spre[0] ;Node* p = (Node *)malloc(sizeof(Node)) ;p->x = rootV ;p->right = p->left = NULL ;root = p ;if(spre == epre){if(sin == ein && *spre == *ein)return true ;else return false ;}int *rootin = sin ;while(rootin < ein && *rootin != rootV) rootin++ ;if(rootin == ein && *rootin != rootV) return false ;int llen = rootin - sin ;bool ret = true ;if(llen > 0)ret = ret && buildsubtree(root->left , spre+1 , spre+llen , sin , rootin-1) ;if(ein - sin - llen > 0)ret = ret && buildsubtree(root->right , spre+llen+1,epre,rootin+1,ein ) ;return ret ;
}bool buildtree(Node*& root , int* pre , int* in , int len){return buildsubtree(root , pre , pre + len - 1, in , in + len - 1) ;
}void PostVisit(Node* root){if(root != NULL){PostVisit(root->left) ;PostVisit(root->right) ;printf("%d ",root->x) ;}
}void Clear(Node* root){if(root != NULL){Node* p = root->left ;Node* q = root->right ;free(root) ;Clear(p) ;Clear(q) ;}
}
int main()
{int n ;while(cin >> n){for(int i = 0;i < n;i++) scanf("%d",&pre[i]) ;for(int i = 0;i < n;i++) scanf("%d",&in[i]) ;Node *root = NULL ;if(buildtree(root , pre , in , n)){PostVisit(root) ;puts("") ;}else{puts("No") ;}Clear(root) ;}return 0;
}

这篇关于JD 1385：重建二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---