vlambda博客
学习文章列表

二叉树模板--剑指offer第4题

来,我们来做题!


剑指offer第4题:

函数签名是:

pre是前序遍历 in是中序遍历public TreeNode reConstructBinaryTree(int [] pre,int [] in)


二叉树的题解法基本就是递归。这题我们也用递归。首先回答两个问题:每次递归做什么?什么条件退出?


每次递归做什么呢?了解前序遍历的同学会知道,前序遍历的结果根节点在左右节点的前面。而中序遍历呢?左节点在根结点左边,右节点在根节点右边。因此二者联系起来就应该满足:举个例子:拿前序遍历结果的第1个元素A,去中序遍历的结果中确定位置,那么这个位置的前面节点就是元素A的左节点,这个位置的后面节点就是元素A的右节点。这样我们就能每次递归构建出一个节点(包含左右子节点),因此可以写出:

int index = 0;for(int i = 0; i < in.length; i++){    找到中序遍历中 和 前序遍历相同的元素    if(in[i] == pre[0]){          index = i;  break; }}根据找到的元素新建节点。TreeNode root = new TreeNode(pre[0]);


什么条件退出呢?很明显当我们每次遍历的前序或者中序数组长度为0的时候退出,当数组长度为1的时候,直接新建节点返回,不需要进行上述步骤。可以写出:

if(pre.length == 0){ return null;}if(pre.length == 1){ return new TreeNode(pre[0]);}


下面我们套模板

二叉树模板

特点:在你需要返回一个二叉树的节点的时候,你必须构造这个二叉树节点,同时需要构建该节点的左右节点:root.left  = , root.right = 这种赋值操作是必须要有的,然后返回构造的节点。同时退出条件一般都会有if(root == null) return null;因此就能写出:

public TreeNode reConstructBinaryTree(int [] pre,int [] in) { if(pre.length == 0){ return null; } if(pre.length == 1){ return new TreeNode(pre[0]); } int index = 0; for(int i = 0; i < in.length; i++){ if(in[i] == pre[0]){ index = i; break; } } TreeNode root = new TreeNode(pre[0]);      该左节点应该为中序遍历的的 元素A的左边 root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,index+1),Arrays.copyOfRange(in,0,index));      该左节点应该为中序遍历的的 元素A的右边 root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,index+1,pre.length),Arrays.copyOfRange(in,index+1,in.length));      返回root给上一层递归      return root; }