正文
[leetcode]_根据二叉树的先序遍历(后序遍历) + 中序遍历 重建二叉树
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
题目1：Construct Binary Tree from Preorder and Inorder Traversal
给定一棵二叉树的先序遍历和中序遍历，求重建二叉树。
思路：
1、先序遍历的第一个节点一定是根节点。
2、在中序遍历中找到该根节点的位置（由中序遍历性质，决定其在中部），将中序遍历数组划分为两段，根节点左端的为左子树部分，相反右端的为右子树部分。
3、由上述左、右子树的长度，决定在先序遍历中，左右子树对应数组的位置。
4、递归 1 ~ 3步，直到子数组长度为1，结束递归。
代码：
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0) return null;
TreeNode root = buildTreeRecursive(preorder , 0 , preorder.length - 1 , inorder , 0 , inorder.length - 1);
return root;
}
public TreeNode buildTreeRecursive(int[] preOrder , int preStart , int preEnd , int[] inOrder , int inStart , int inEnd){
int value = preOrder[preStart];
//1、先序遍历中的第一个节点一定是根节点。
TreeNode node = new TreeNode(value);
//结束条件：如果长度为1，则返回该节点。
if(preStart == preEnd) return node;
//2、在中序遍历中查找该节点的位置。
int index = 0;
for(index = inStart ; index <= inEnd && inOrder[index] != value; ){ index++; }
//3、确定左右子树对应数组的位置后，递归调用。
int leftLen = index - inStart;
int rightLen = inEnd - index;
if(leftLen > 0){
node.left = buildTreeRecursive(preOrder , preStart + 1 , preStart + leftLen , inOrder , inStart , index - 1);
}
if(rightLen > 0){
node.right = buildTreeRecursive(preOrder , preEnd - rightLen + 1 , preEnd , inOrder , index + 1 , inEnd);
}
return node;
}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
题目二：Construct Binary Tree from Inorder and Postorder Traversal
给定一棵二叉树的中序遍历和后序遍历，重建二叉树。其思路与题目一完全一样。只是从postOrder确定根节点的位置，然后同样放到inOrder中去划分左右子树。
代码：
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder == null || postorder == null || inorder.length == 0 || postorder.length == 0) return null;
TreeNode root = buildTreeRecursive(inorder , 0 , inorder.length - 1 , postorder , 0 , postorder.length - 1);
return root;
}
public TreeNode buildTreeRecursive(int[] inOrder , int inStart , int inEnd ,
int[] postOrder , int postStart , int postEnd){
int value = postOrder[postEnd];
TreeNode node = new TreeNode(value);
if(postStart == postEnd) return node; // only one node
int index = -1;
for(index = inStart ; index <= inEnd && inOrder[index] != value ; index++); // find in inOrder
int leftLen = index - inStart;
if(leftLen > 0){
node.left = buildTreeRecursive(inOrder , inStart , index - 1 , postOrder , postStart , postStart + leftLen - 1);
}
int rightLen = inEnd - index;
if(rightLen > 0){
node.right = buildTreeRecursive(inOrder , index + 1 , inEnd , postOrder , postEnd - rightLen , postEnd - 1);
}
return node;
}
这两道题思路理清了，到也很流畅。：)
