中序序列

[编程题]中序序列

热度指数：129 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一棵有n个结点的二叉树的先序遍历与后序遍历序列，求其中序遍历序列。
若某节点只有一个子结点，则此处将其看作左儿子结点

示例1

输入

5,[3,2,1,4,5],[1,5,4,2,3]

输出

[1,2,5,4,3]

说明

备注:

算法知识视频讲解

勇敢牛牛，不怕困难！

struct TreeNode* buildTree(int* pre, int* post, int i, int j, int n) {
  if (n <= 0) return NULL;
  struct TreeNode* root = (struct TreeNode*) malloc(sizeof(struct TreeNode));
  root->val = *(pre + i);
  root->left = root->right = NULL;
  if (n == 1) return root;
  
  int k = j;
  while (*(post + k) != *(pre + i + 1)) ++k;
  int l = k - j + 1; // the length of left sub tree
   
  root->left  = buildTree(pre, post, i + 1, j, l);
  root->right = buildTree(pre, post, i + 1 + l, k + 1, n - 1 - l);
  return root;
}

void inorderTraversal(struct TreeNode* root, int* ans, int* ansSize) {
  if (!root) return;
  inorderTraversal(root->left, ans, ansSize);
  *(ans + (*ansSize)++) = root->val;
  inorderTraversal(root->right, ans, ansSize);
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int 二叉树节点数量
 * @param pre int一维数组 前序序列
 * @param preLen int pre数组长度
 * @param suf int一维数组 后序序列
 * @param sufLen int suf数组长度
 * @return int一维数组
 * @return int* returnSize 返回数组行数
 */
int* solve(int n, int* pre, int preLen, int* suf, int sufLen, int* returnSize) {
  *returnSize = 0;
  int* ans = (int*) malloc(n * sizeof(int));
  if (!ans) return NULL;
  
  struct TreeNode* root = buildTree(pre, suf, 0, 0, n);
  inorderTraversal(root, ans, returnSize);
  return ans;
}

发表于 2021-07-17 11:24:48 回复(0)

Python 3

牛主ss

有大佬帮忙看看哪错了吗，python写的，就是先建立好树再中序遍历一下，最后一个用例没过。。。

class Tree:

def __init__(self,x):
self.val=x
self.left=None
self.right=None
class Solution:
def solve(self , n , pre , suf ):
res=[]
def jian(prel,sufl,root):
if not prel:return
try:l=Tree(prel[1])
except:return
r=Tree(sufl[-2])
if l.val==r.val:root.left=l
else:
root.left=l
root.right=r
a=sufl.index(prel[1])
sufl2=sufl[:a+1]
sufl3=sufl[a+1:-1]
prel2=prel[1:a+2]
prel3=prel[a+2:]
jian(prel2,sufl2,l)
jian(prel3,sufl3,r)
root0=Tree(pre[0])
jian(pre,suf,root0)
def zhong(root):
if not root:return
zhong(root.left)
res.append(root.val)
zhong(root.right)
zhong(root0)
return res

发表于 2021-09-29 09:44:23 回复(0)