剑指Offer4——根据二叉树的先序遍历和中序遍历构造二叉树

2021年9月28日 6点热度 0条评论 来源: 满头白发的菜鸡

该文对剑指Offer的第四题根据二叉树的先序和中序遍历构造二叉树

题目描述
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
示例
输入:
前序遍历:[1,2,3,4,5,6,7]
中序遍历:[3,2,4,1,6,5,7]
输出:
二叉树:{1,2,5,3,4,6,7}

想要做出该题,首先应该知道二叉树的前、中、后遍历。(下面简单说下三个遍历)
:先输出根节点,在输出左孩子,然后输出右孩子(遍历序列的第一个数就是整个树的根节点)
:先输出左孩子,在输出根节点,最后输出右孩子(根节点在左右子树之间,可根据前序和后序中已知的根节点进行划分子树)
:先输出左孩子,在输出右孩子,然后输出根节点(遍历序列的倒数第一个数就是整个树的根节点)

好了,基本知识了解了,下一步做题吧
该题解法是模拟人工重构二叉树的方式进行求解
为了方便讲解,本人已将示例中的二叉树画出,如下图(很丑)

我们都知道前序遍历第一个数就是整个树的根节点,根据根节点可以将整个树分为左子树和右子树,即可根据根节点的值从中序遍历的序列中找出左右子树的中序遍历的序列,依次类推,即可重新构建。

看完上面的分析,大多数人可以想到递归遍历算法,通过划分左右子树的方式递归,直到空集。但是怎么写代码呢?
下面给出两种递归求解方法:
方法1:值传递递归(通过复制左右子树的值进行求解)

public TreeNode reConstructBinaryTree1(int [] pre,int [] in) { 
        if(pre == null || in == null || pre.length == 0 || in.length == 0) { 
        	return null;
        }
        if(pre.length != in.length) { 
        	return null;
        }
        TreeNode root = new TreeNode(pre[0]);//根节点
        for(int i = 0; i < pre.length; i++) { //根据中序序列查找划分下标
        	if(pre[0] == in[i]) { 
        		root.left = reConstructBinaryTree2(Arrays.copyOfRange(pre, 1,i+1),Arrays.copyOfRange(in, 0,i));
        		root.right = reConstructBinaryTree2(Arrays.copyOfRange(pre, i+1, pre.length),Arrays.copyOfRange(in, i+1, in.length));
        	}
        }
        return root;
    }

我们直到pre[0]是整个树的根节点,因此在中序遍历序列in[]中找到根节点的位置,就可以根据该位置划分左右子树。重复这个过程即可(代码中的for循环就是)

方法2:遍历序列的边界值递归

    public TreeNode reConstructBinaryTree2(int [] pre,int [] in) { 
        if(pre == null || in == null || pre.length == 0 || in.length == 0) { 
        	return null;
        }
    	return helper(pre,0,pre.length-1,in,0,in.length-1);
    }
    
    public TreeNode helper(int[] preOrder, int preL, int preR, int[] inOrder, int inL, int inR) { 
    	if(preL > preR || inL > inR) { 
    		return null;
    	}
    	int rootVal = preOrder[preL];
    	int index = 0;
    	while( index <= inR && inOrder[index] != rootVal) { 
    		index++;
    	}
    	TreeNode root = new TreeNode(rootVal);
    	root.left = helper(preOrder,preL+1,preL-inL+index,inOrder,inL,index);
    	root.right = helper(preOrder,preL-inL+index+1,preR,inOrder,index+1,inR);
    	return root;
    }

解题思路一样,重点是边界值怎么确定,即方法helper(int[] preOrder, int preL, int preR, int[] inOrder, int inL, int inR)里的参数怎么求?
第一次看到这个方法的时候也很萌币,尤其是那一堆表达式,例如preL-inL+index,为什么右边界是它啊?
看了好几个相关博主的解答,也没有说明的,甚至提出了只可意会不可传!但是这难不倒我!(得意地笑)
将式子preL-inL+index中的数改改位置,变为preL+(index-inL),这下明白了吧?
不明白?好,那就让聪明的小菜鸟再说的透骨点。
根据根节点在中序遍历序列中划分左右子树后,由于划分后左右子树的中的节点数都是固定的了,因此在先序遍历的序列中与根节点相邻的x个数就是左子树中的节点,然后剩下的就是右子树的节点,这个左子树个数x怎么求?当然是根据中序遍历的左边界和根节点来求啊!所以。。。还不懂的话就拉出去枪毙五分钟吧。。。

本题后面还有个扩展,是让通过中序和后序重构二叉树。思路一样,具体不在复述,直接上代码:

    public static TreeNode reConstructBinaryTreeByInOrderAndPostOrder(int[] in, int[] post) { 
    	if(in.length == 0 || in == null || post.length == 0 || post == null || (in.length != post.length)) { 
    		return null;
    	}
    	TreeNode root = new TreeNode(post[post.length-1]);
    	for(int i = 0; i < in.length; i++) { 
    		if(post[post.length-1] == in[i]) { 
    	    	root.left = reConstructBinaryTreeByInOrderAndPostOrder(Arrays.copyOfRange(in, 0, i),Arrays.copyOfRange(post, 0, i));
    	    	root.right = reConstructBinaryTreeByInOrderAndPostOrder(Arrays.copyOfRange(in, i+1, in.length),Arrays.copyOfRange(post, i, post.length-1));
    		}
    	}
    	return root;

    }

我是菜鸡程序猿,菜鸡程序猿就是我!谢谢各位

    原文作者:满头白发的菜鸡
    原文地址: https://blog.csdn.net/ming19951009/article/details/110873783
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。