大家都知道二叉树已知中序遍历和后序遍历可以求前序遍历
已知前序遍历和中序遍历可以求后序遍历,那么现在实现一下
想法基本是利用递归,先找到根节点的位置,然后利用左右子树递归
前序遍历+中序遍历 求 后序遍历:
void dfs(char *inorder,char *preorder,int len){if(len == 0) return ;int rootindex = 0;while(rootindex<len){if(inorder[rootindex] == preorder[1])break;
rootindex++;}dfs(inorder,preorder+1,rootindex);dfs(inorder+rootindex+1,preorder+rootindex+1,len-1-rootindex);printf("%c\n",*inorder );
}
中序遍历+后序遍历-->先序遍历
void dfs(char *inorder,char*preorder,int len){if(len == 0) return ;int rootindex = 0;printf("%c\n",postorder[len-1]);while(rootindex<len){if(inorder[rootindex]==postorder[len-1])break;rootindex++;}dfs(inorder,postorder,rootindex);dfs(inorder+rootindex+1,postorder+rootindex,len-1-rootindex);
}