剑指offer7:重建二叉树 墨蓝 2022-02-19 09:07 136阅读 0赞 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序遍历序列\{4,7,2,1,5,3,8,6\},则重建二叉树并返回。 思路:用到了树,一般采用递归的方法来解题,其次就是本题有分治法的思想在里面。首先将一个大问题,分解成2个小问题,左子树和右子树,数据规模减少,但是处理的方法一样。所以就能使用递归技术。而2个左右子树又能继续分解。这个还是看限定条件才行。 首先从前序序列第一个节点就是整个树的根节点,那么指向中序遍历中的根节点,它的左边就是左子树,那么它的右边就是右子树。那么从二分查找入手就能得到较为直观的看法。 伪代码 : xx判断递归的终点, 其次就是递归处理左子树 再递归吃处理右子树 返回根节点 递归过程就是:从前序遍历数组的第一个,再去遍历到中序遍历的那个i,再从i切分,分别root.left = rebuid(),root.right=rebuild();中途,利用Arrays.copyOfRange(pre,i,i+1)函数切分,把pre,分i,i+1. 便于理解的代码 public TreeNode reConstructBinaryTree(int [] pre,int [] in) { if (pre.length == 0 || in.length == 0) { return null; } TreeNode root = new TreeNode(pre[0]); // 在中序中找到前序的根 for (int i = 0; i < in.length; i++) { if (in[i] == pre[0]) { // 左子树,注意 copyOfRange 函数,左闭右开 root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i)); // 右子树,注意 copyOfRange 函数,左闭右开 root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length)); break; } } return root; } 而 后序遍历+中序遍历构建二叉树 // 后序 和中序 public TreeNode ConstructLater(int[] lat,int[] in) { if(lat == null || lat.length ==0 || in ==null || in.length == 0) return null; // 构建根节点 // 前序遍历拿根节点 int rootval = lat[lat.length-1]; TreeNode root = new TreeNode(rootval); // 在中序遍历找到根节点切分成2个左右子序列 for(int i = 0;i<in.length;i++) { if(rootval == in[i]) { // 开始递归左子树构建 root.left = ConstructLater(Arrays.copyOfRange(lat,0,i),Arrays.copyOfRange(in,0,i)); // 递归构建右子树 root.right = ConstructLater(Arrays.copyOfRange(lat,i,lat.length-1),Arrays.copyOfRange(in,i+1,in.length)); break; } } return root; }
还没有评论,来说两句吧...