剑指offer之重建二叉树

1 问题

重建二叉树：给定二叉树的先序遍历（根左右）和中序（左中右）遍历结果，建立这棵二叉树。输入保证二叉树无重复结点

以先序{1, 2, 4, 7, 3, 5, 6, 8}和中序{4, 7, 2, 1, 5, 3, 8, 6}为例

2 分析

先序遍历的特点，我们知道{1, 2, 4, 7, 3, 5, 6, 8}第一个元素1就是树的根节点，然后中序遍历{4, 7, 2, 1, 5, 3, 8, 6}的根节点在中间，因为我们从先序遍历里面得知1就是根节点，所以在中序遍历{4, 7, 2, 1, 5, 3, 8, 6}中，在中序遍历数组1的左边元素都是根节点左子树{4, 7, 2,}，这里是3个元素，所以在先序数组里面根节点1的后面3个元素也是左子树{2,4,7}，也是根节点的左子树，在中序遍历1的右边边元素都是{5, 3, 8, 6}都是根节点的右子树，然后我们在先序数组里面根节点1的后面第3个元素的后面到尾巴，也就是{3,5,6,8}也就是根节点的右子树。然后我们再把问题分解成构建左子树{2,4,7}和构建右子树{3,5,6,8}，以此递归处理。

我们构建左子树

再构建右子树

3 代码实现

import java.io.*;

class Tree
{
    public int value;
    public Tree left;
    public Tree right;

    public Tree(int value)
    {
        this.value = value;
        this.left = null;
        this.right = null;
    }

    /**
     *前序遍历
     */
    public void printTree(Tree node)
    {
        if (null == node)
            return;
        System.out.println("value is " + node.value);
        printTree(node.left);
        printTree(node.right);
    }

    /*
     *得到树的根节点
     */
    public Tree getTree(int[] preDatas, int[] inDatas)
    {
        if (null == preDatas || null == inDatas)
        {
            System.out.println("preDatas is null or inDatas is null");
            return null;
        }
        Tree tree = buildTree(preDatas, 0, preDatas.length - 1, inDatas, 0, inDatas.length - 1);
        return tree;
    }

    /*
     *构建树的左右子结构
     */
    public Tree buildTree(int[] preDatas, int preStart, int preEnd, int[] inDatas, int inStart, int inEnd)
    {
        if (null == preDatas || null == inDatas)
        {
            System.out.println("preDatas is null or inDatas is null");
            return null;
        }
        System.out.println("preStart is:" + preStart + " preEnd is" + preEnd + " inStart is " + inStart + " inEnd is" + inEnd);
        //这里就是进行如果树的左子节点和右子节点是否为空进行设置
        if (preStart > preEnd || inStart > inEnd)
        {
            return null;
        }
        Tree tree = new Tree(preDatas[preStart]);
        for (int i = inStart; i <= inEnd; ++i)
        {
            System.out.println("preDatas[preStart] is " + preDatas[preStart]);
            if (preDatas[preStart] == inDatas[i])
            {
                tree.left = buildTree(preDatas, preStart + 1, preStart + i - inStart, inDatas, inStart, i - 1);
                tree.right = buildTree(preDatas, preStart + i - inStart + 1, preEnd, inDatas, i + 1, inEnd);
                break;
            }
        }
        return tree;
    }
}

class test
{
public static void main (String[] args) throws java.lang.Exception
{
    int[] preDatas = {1, 2, 4, 7, 3, 5, 6, 8};
            int[] inDatas = {4, 7, 2, 1, 5, 3, 8, 6};
            Tree test =  new Tree(0);
            Tree tree = test.getTree(preDatas, inDatas);
            if (tree == null)
            {
                System.out.println("tree is null");
                return;
            }
            //我们进行前序打印树
            test.printTree(tree);

}
}

4 运行结果

preStart is:0 preEnd is7 inStart is 0 inEnd is7
preDatas[preStart] is 1
preDatas[preStart] is 1
preDatas[preStart] is 1
preDatas[preStart] is 1
preStart is:1 preEnd is3 inStart is 0 inEnd is2
preDatas[preStart] is 2
preDatas[preStart] is 2
preDatas[preStart] is 2
preStart is:2 preEnd is3 inStart is 0 inEnd is1
preDatas[preStart] is 4
preStart is:3 preEnd is2 inStart is 0 inEnd is-1
preStart is:3 preEnd is3 inStart is 1 inEnd is1
preDatas[preStart] is 7
preStart is:4 preEnd is3 inStart is 1 inEnd is0
preStart is:4 preEnd is3 inStart is 2 inEnd is1
preStart is:4 preEnd is3 inStart is 3 inEnd is2
preStart is:4 preEnd is7 inStart is 4 inEnd is7
preDatas[preStart] is 3
preDatas[preStart] is 3
preStart is:5 preEnd is5 inStart is 4 inEnd is4
preDatas[preStart] is 5
preStart is:6 preEnd is5 inStart is 4 inEnd is3
preStart is:6 preEnd is5 inStart is 5 inEnd is4
preStart is:6 preEnd is7 inStart is 6 inEnd is7
preDatas[preStart] is 6
preDatas[preStart] is 6
preStart is:7 preEnd is7 inStart is 6 inEnd is6
preDatas[preStart] is 8
preStart is:8 preEnd is7 inStart is 6 inEnd is5
preStart is:8 preEnd is7 inStart is 7 inEnd is6
preStart is:8 preEnd is7 inStart is 8 inEnd is7
value is 1
value is 2
value is 4
value is 7
value is 3
value is 5
value is 6
value is 8

5 总结

中途遇到这个一个错误

error: <identifier> expected

是我在手写函数的时候参数前面忘记了定义类型，所以报这个错误。

我们这里用了4个指针，分别是先序的起尾指针和中序的起尾指针，然后我们不断更新4个指针指针的位置，然后当先序的起指针大于尾指针的时候或者中序的起指针大于尾指针的时候我们就构建空指针，就这样递归处理就行。