leetcode106 根据中序遍历和后序遍历如何还原二叉树?
public class ConstructBinaryTreeFromInorderAndPostorderTraversal
{
int pInorder; // index of inorder array
int pPostorder; // index of postorder array
private TreeNode buildTree(int[] inorder, int[] postorder, TreeNode end) {
if (pPostorder < 0) {
return null;
}
// create root node
TreeNode n = new TreeNode(postorder[pPostorder--]);
// if right node exist, create right subtree
if (inorder[pInorder] != n.val) {
n.right = buildTree(inorder, postorder, n);
}
pInorder--;
// if left node exist, create left subtree
if ((end == null) || (inorder[pInorder] != end.val)) {
n.left = buildTree(inorder, postorder, end);
}
return n;
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
pInorder = inorder.length - 1;
pPostorder = postorder.length - 1;
return buildTree(inorder, postorder, null);
}
public static void main(String[] args) {
int[] a = new int[]{
1,2,3,4,5,6,7
} ;
int[] b = new int[]{
1,3,2,5,7,6,4
} ;
TreeNode t = new ConstructBinaryTreeFromInorderAndPostorderTraversal().buildTree(a , b) ;
System.out.println(t);
}
}
这个是leetcode地址: https://leetcode.com/problems...
该如何理解这个算法?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论