恢复二叉树

2020-07-04

恢复二叉树

如题所示，我们解决的问题是根据二叉树的遍历组合来还原这个二叉树，这个过程其实是复杂的，我们需要根据三种遍历方式的不同特性来确定这个二叉树，由于前序+后序遍历无法确定一颗唯一的二叉树，所以我们将着重介绍两种：前序+中序和后序+中序来还原二叉树.

接下来我将详细介绍后序+中序还原二叉树的过程

例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

首先我们根据后序遍历的特点可知，最后一个元素就是数的根节点，根据中序遍历可知，根节点的左侧是左子树，右侧是右子树：

接下来解释一下下面会使用到的一些变量：

int InStart  //接下来递归时我们使用到的中序遍历的左边界
int InEnd    //中序便利的右边界
int PostStart //后序遍历的左边界
int PostEnd  //后序遍历的有边界

接下来最重要的是边界的计算：

1.左子树的中序数组左边界：Instart，有边界是rootIndex-1
2.左子树的后序数组左边界：PostStart，右边界：PostStart+（rootIndex-1-Instart+1）-1
3.右子树的中序数组左边界：rootIndex+1，右边界InEnd
4.右子树的中序数组左边界：：PostStart+rootIndex-Instart，右边界：PostEnd-1
所以接下来代码实现：

public class InAndPost {
	int[] postArr;
	Map<Integer,Integer> map = new HashMap<>();//利用hash表快速找到根节点在中序数组中的位置
	public static void main(String[] args) {
		// TODO 自动生成的方法存根

	}
	public TreeNode buildTree(int[] inorder, int[] postorder) {
		postArr = postorder;
		for(int i=0;i<inorder.length;i++) {
			map.put(inorder[i], i);
		}
		return buildTrees(0, inorder.length-1, 0, postArr.length-1);
    }
	public TreeNode buildTrees(int InStart,int InEnd,int PostStart,int PostEnd) {
		if(InStart>InEnd||PostStart>PostEnd) {
			return null;
		}
		int root = postArr[PostEnd];
		int rootIndex = map.get(root);
		TreeNode node = new TreeNode(root);
		node.left = buildTrees(InStart, rootIndex-1, PostStart, PostStart+rootIndex-InStart-1);
		node.right = buildTrees(rootIndex+1, InEnd, PostStart+rootIndex-InStart, PostEnd-1);
		return node;
	}

}

接下来是前序+中序:

其实大部分和前者的思路一致，最主要是边界的求法不同
中序遍历中，我们知道左子树：[inorder_start,index-1], 右子树：[index+1, inorder_end]
在前序遍历中，左子树起始位置为pre_start+1,左子树一共有(index-1 - inorder_start)个，因此左子树：[pre_start+1, pre_start+1 + (index-1 - inorder_start)]
右子树起始位置为左子树终止位置+1，终止位置为pre_end，因此右子树：[ pre_start+1 + (index-1 - inorder_start) + 1, pre_end]

class Solution {
    int[] postArr;
    Map<Integer,Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postArr = postorder;
		for(int i=0;i<inorder.length;i++) {
			map.put(inorder[i], i);
		}
		return buildTrees(0, inorder.length-1, 0, postArr.length-1);
    }
    public TreeNode buildTrees(int InStart,int InEnd,int PostStart,int PostEnd) {
		if(InStart>InEnd||PostStart>PostEnd) {
			return null;
		}
		int root = postArr[PostEnd];
		int rootIndex = map.get(root);
		TreeNode node = new TreeNode(root);
		node.left = buildTrees(InStart, rootIndex-1, PostStart, PostStart+rootIndex-InStart-1);
		node.right = buildTrees(rootIndex+1, InEnd, PostStart+rootIndex-InStart, PostEnd-1);
		return node;
	}

}