帮你从算法的角度来认识二叉树---（二）

引言在上文中提到了前序遍历、中序遍历、后序遍历其中有一类算法题离不开这三种遍历方式就是从前序与中序遍历序列中构造出二叉树反向推导、从后序与中序遍历序列中构造出二叉树那能不能从前序与后序遍历序列中构造出二叉树呢答案是不能原因前序根 → 左 → 右中序左 → 根 → 右后序左 → 右 → 根在这三个序列里只有中序能够把左右子树给分开再搭配一个前序或后序把根节点找到这样就能实现左子树、根节点、右子树的判别这个知识点非常重要算法题1105.从前序与中序遍历序列构造二叉树示例思路利用递归思想哈希表来实现首先先确定根节点前序数组的第一个元素就是当前子树的根在中序数组中顶为根节点用哈希表提前存好中序数组的值-下标实现O1快速查找找到根后左边所有元素 左子树右边所有元素 右子树计算左子树节点数量根节点在中序数组的下标-中序左边界递归构建左右子树根据刚才求得的左子树大小把前序和中序都划分成左子树区间、右子树区间递归构建左右子树再挂到当前根节点上递归终止条件当前区间左边界右边界返回null这里用到哈希表是因为可以直接定位到根节点的位置降低了时间复杂度代码/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { private MapInteger,Integer indexMap; public TreeNode buildTree(int[] preorder, int[] inorder) { int npreorder.length; indexMapnew HashMapInteger,Integer(); for(int i0;in;i){ indexMap.put(inorder[i],i); } return myBuildTree(preorder,inorder,0,n-1,0,n-1); } public TreeNode myBuildTree(int[] preorder,int[] inorder,int preorder_left,int preorder_right,int inorder_left,int inorder_right){ if(preorder_leftpreorder_right){ return null; } int preorder_rootpreorder_left; //找到根节点在中序遍历的下标 int inorder_rootindexMap.get(preorder[preorder_root]); TreeNode rootnew TreeNode(preorder[preorder_root]); int size_left_subtreeinorder_root-inorder_left; //构造左子树 root.leftmyBuildTree(preorder,inorder,preorder_left1,preorder_leftsize_left_subtree,inorder_left,inorder_root-1); //构造右子树 root.rightmyBuildTree(preorder,inorder,preorder_leftsize_left_subtree1,preorder_right,inorder_root1,inorder_right); return root; } }算法题2106.从中序与后序遍历序列构造二叉树示例思路和利用前序中序实现二叉树的构建思路是完全一样的只不过根节点在后序数组的最后一位只需要在原来的基础上更换一下坐标即可代码/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { private MapInteger,Integer indexMap; public TreeNode buildTree(int[] inorder, int[] postorder) { int ninorder.length; indexMapnew HashMapInteger,Integer(); for(int i0;in;i){ indexMap.put(inorder[i],i); } return myBuildTree(inorder,postorder,0,n-1,0,n-1); } public TreeNode myBuildTree(int[] inorder,int[] postorder,int inorder_left,int inorder_right,int postorder_left,int postorder_right){ if(postorder_leftpostorder_right){ return null; } int postorder_rootpostorder_right; int inorder_rootindexMap.get(postorder[postorder_root]); TreeNode rootnew TreeNode(postorder[postorder_root]); int size_left_subTreeinorder_root-inorder_left; root.leftmyBuildTree(inorder,postorder,inorder_left,inorder_root-1,postorder_left,postorder_leftsize_left_subTree-1); root.rightmyBuildTree(inorder,postorder,inorder_root1,inorder_right,postorder_leftsize_left_subTree,postorder_right-1); return root; } }小舟有话说这篇只讲了一种题型下一篇还会讲一下其他剩余常见算法题~