洛谷P1827 美国血统

url: https://www.luogu.com.cn/problem/P1827

tag:
递归, 二叉树

代码:

  1. #include <iostream>
  2. #include <string>
  3. using namespace std;
  4. string inorder, preorder;
  5. void buildPostorder(int inStart, int inEnd, int preStart, int preEnd) {
  6. // 若范围无效,则返回
  7. if (inStart > inEnd || preStart > preEnd) {
  8. return;
  9. }
  10. // 前序遍历的第一个元素即为根节点
  11. char root = preorder[preStart];
  12. // 在中序遍历中找到根节点的位置
  13. int rootIndex = -1;
  14. for (int i = inStart; i <= inEnd; ++i) {
  15. if (inorder[i] == root) {
  16. rootIndex = i;
  17. break;
  18. }
  19. }
  20. // 根节点左边的节点个数
  21. int leftTreeSize = rootIndex - inStart;
  22. // 递归处理左子树
  23. buildPostorder(inStart, rootIndex - 1,
  24. preStart + 1, preStart + leftTreeSize);
  25. // 递归处理右子树
  26. buildPostorder(rootIndex + 1, inEnd,
  27. preStart + leftTreeSize + 1, preEnd);
  28. // 最后输出根节点,实现后序遍历顺序:左子树 -> 右子树 -> 根
  29. cout << root;
  30. }
  31. int main() {
  32. // 输入中序遍历和前序遍历字符串
  33. cin >> inorder >> preorder;
  34. int n = inorder.size();
  35. buildPostorder(0, n - 1, 0, n - 1);
  36. return 0;
  37. }
添加新评论