首页 > 代码库 > 【leetcode】Construct Binary Tree from Inorder and Postorder Traversal
【leetcode】Construct Binary Tree from Inorder and Postorder Traversal
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
题解：如下图所示的一棵树：
5 / 2 4 / \ 1 3 6
中序遍历序列：1 2 3 5 4 6
后序遍历序列：1 3 2 6 4 5
后序遍历序列的最后一个元素就是当前根节点元素。首先想到的方法是递归，重要的是在先序和中序序列中分清楚哪一部分是左子树的，哪一部分是右子树的。
递归的过程如下图所示：其中in和po分别代表递归调用时传递给左子树的中序遍历序列和后序遍历序列。
以第一次递归为例，说明左右子树的中序和后序遍历序列如何求：
如上图所示，现在中序序列中找到根节点的位置(5)，就能够知道左子树(绿色圈)和右子树(橙色圈)的中序遍历序列了。然后根据中序遍历的长度等于后序遍历的长度，计算出左右子树的后序遍历序列，递归调用构造树函数即可。
代码如下：
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */10 public class Solution {11 public int InorderIndex(int[] inorder,int key){12 if(inorder == null || inorder.length == 0)13 return -1;14 15 for(int i = 0;i < inorder.length;i++)16 if(inorder[i] == key)17 return i;18 19 return -1;20 }21 public TreeNode buildTreeRec(int[] inorder,int[] postorder,int instart,int inend,int postart,int poend){22 if(instart > inend)23 return null;24 TreeNode root = new TreeNode(postorder[poend]);25 int index = InorderIndex(inorder, root.val);26 root.left = buildTreeRec(inorder, postorder, instart, index-1, postart, postart+index-instart-1);27 root.right = buildTreeRec(inorder, postorder, index+1, inend, postart+index-instart, poend-1);28 29 return root;30 }31 public TreeNode buildTree(int[] inorder, int[] postorder) {32 return buildTreeRec(inorder, postorder, 0, inorder.length-1, 0, postorder.length-1);33 }34 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。