Construct Binary Tree

Leave a comment

December 14, 2016 by oneOokay

  1. 由preorder和inorder的顺序来重建树:可以建立一个unique general binary tree
  2. 由postorder和inorder的顺序来重建树:可以建立一个unique general binary tree
  3. 由preorder和postorder的顺序来重建树:只能够建立一个unique full binary tree.
    • {A, B, #}和{A,#,B}的preorder都是一样的AB;postoder都是一样的BA

pre-order & in-order: 我能够想到的是用recursive来做,且由preorder可以找到root,在inorder中找到root在的地方,此处之前就是该root的左子树,此处之后就是该root的右子树。但是因为当时对recursion不熟,于是卡住了!没有想清楚的地方就是:不知道怎么写recursive,不知道以哪个array为主遍历,不知道recursive的里面要传入什么:

  • 首先要想到“在inorder中找到root在的地方,此处之前就是该root的左子树,此处之后就是该root的右子树。”这里其实是有范围的,有一个inorder array的起点和终点,这个起点和终点和“此处”决定了当前的node和它的左右子树。
  • 需要以preorder来作为遍历

然后想通了上面的两点之后就知道了recursive至少要有三个parameter:

  • preorder当前的index:要处理的当前的一个值,将要把它变为root
  • inorder的Start和End:preorder[index]的值会在inorder[start]和inorder[end]之间(包含关系)。也就是inorder[start]和inorder[end]之间的数字是以preorder[index]为root的一个子树的所有的元素。

对于recursive method我们要注意的是:

  • return condition:这里return null的情况是:当前的node是个null,也就是根据各种index invalid,在preorder和inorder中不存在对应的值。注意并不能取等!
  • 由preorder可知顺序是Root->Left->Right:所以preindex + 1就是该root的左子树的root;preindex + 1 + 1并不是该root的右子树的root.那么要如何找到该root的右子树的root呢?
      • preIndex+(root的左子树的所有元素的个数) + 1就以preIndex为root的右儿子的index
  • 该root的所有左子树的元素的个数就可以在inorder里面找到:是index – start
  • 所以右儿子的index为: preIndex + (index – start) + 1

感觉我抽象思维较差啊:

  • 当node.left == null的时候,helper(pre, start, end)中:pre可能是valid的,因为可能是root的右儿子;但是start和end一定是invalid
  • 当node.right == null的时候,helper(pre, start, end)中:pre,start和end一定都是invalid的
    private int[] pre;
    private int[] in;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0 || inorder.length == 0){
            return null;
        }
        pre = preorder;
        in = inorder;
        return helper(0, 0, inorder.length - 1);
    }
    
    private TreeNode helper(int preIndex, int inStart, int inEnd){
        if (preIndex > pre.length - 1 || inStart > inEnd){
            return null;
        }
        int index = 0;
        for (int i = inStart; i <= inEnd; i ++){
            if (in[i] == pre[preIndex]){
                index = i;
                break;
            }
        }
        TreeNode node = new TreeNode(pre[preIndex]);
        node.left = helper(preIndex + 1, inStart, index - 1);
        node.right = helper(preIndex + index - inStart + 1, index + 1, inEnd);
        return node;
    }

post-order & in-order:

  • 注意并不是post-order反过来就是pre-order的:post:left->right->root; pre:root->left->right.
  • 所以并不是翻转post-order的顺序直接套用inorder的method.而是应该:
    • 从postorder的最后一位开始遍历,因为root都在最后
    • 先构造root的右儿子: 如果存在的话一定是postIndex – 1
    • 再构造root的左儿子:index就是postIndex – root的右子树的所有的node的数量 – 1
      • postIndex – (end – index) – 1.
    public TreeNode buildTree(int[] postorder, int[] inorder) {
        ...
        return helper(postorder.length - 1, 0, inorder.length - 1);
    }
    
    private TreeNode helper(int postIndex, int inStart, int inEnd){
        if (postIndex < 0 || inStart > inEnd){
            return null;
        }
        ...
        TreeNode node = new TreeNode(pre[preIndex]);
        node.right = helper(postOrder - 1, index + 1, end);
        node.left = helper(postOrder - (inEnd - index) - 1, start, index - 1);
        return node;
    }

preorder和postorder:

  • 需要一个全局变量指针preIndex来遍历preorder
  • 在preorder中按顺序遍历. 对于当前的preIndex,新建一个node.
  • preIndex ++,指针移到下一个preorder顺序的点.在postorder中找到该点的index.
  • 从而[start,index]为node左子树;[index + 1,end – 1]为node的右子树
private char[] pre;
private char[] post;
private int preIndex;
public void build(char[] pre, char[] post){
	this.pre = pre;
	this.post = post;
	preIndex = 0;
	TreeNode root = helper(0, pre.length - 1);
	}
	
private TreeNode helper(int start, int end){
	if (preIndex > pre.length - 1 || start > end) return null;
	TreeNode node = new TreeNode(pre[preIndex ++]);
	if (preIndex > pre.length - 1 || start == end) return node;
	int index = findNext(pre[preIndex]);
	if (index < start || index > end) return node;
	node.left = helper(start, index);
	node.right = helper(index + 1, end - 1);
	return node;
}
	
private int findNext(char c){
	for (int i = 0; i < post.length; i ++){
		if (post[i] == c) return i;
	}
	return - 1;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: