【中序、后序遍历序列】【前序、中序遍历序列】构造二叉树

大家好，欢迎来到IT知识分享网。

前置知识

• 第1点：每一个节点都可以看作一棵树的根节点。
• 第2点：掌握前序、中序、后序遍历顺序。前序遍历：根左右，中序遍历：左根右，后序遍历：左右根。
• 第3点：掌握双指针或者说滑动窗口，窗口所承载的是左子树或右子树。
• 第4点：中序序列的作用是区分左右子树，如若我们得到根节点的位置，就可以知道该节点的左部分为左子树，右部分为右子树。而根节点的位置我们可以通过前序序列或后序序列得到（在这里再次声明第1点知识）。

【中序、后序遍历序列】构造二叉树

class Solution { 
    Map<Integer,Integer> map=new HashMap<>(); int post_idx; int[] inorder,postorder; public TreeNode buildTree(int[] inorder, int[] postorder) { 
    this.inorder=inorder; this.postorder=postorder; //在接下来的helper方法中用于按顺序从右向左获取后序序列中的值 //也在接下来的for循环中充当中序序列值的索引 post_idx=-1; //为中序序列添加映射，以便在接下来用于通过val得到其在中序序列的索引下标 for(Integer val:inorder){ 
    post_idx++; map.put(val,post_idx); } return helper(0,post_idx); } public TreeNode helper(int left,int right){ 
    //[left,right]是一个作用于中序序列的下标区间,该区间表示一棵树 //该区间内一定有一个节点是该树的根节点 //当left>right表示不存在该树。返回null if(left>right){ 
    return null; } //获取后序序列中的索引下标为post_idx的值 int val=this.postorder[post_idx]; //创建节点 TreeNode root=new TreeNode(val); //通过val获取该节点在中序序列的位置 int idx=map.get(val); post_idx--; //idx是我们获得的在中序序列的索引下标，它的右边即为右子树，左边即为左子树 root.right=helper(idx+1,right); root.left=helper(left,idx-1); return root; } } 

注意：在【中序、后序遍历序列】构造二叉树时，需先构造右子树，这是由于后序序列的特性决定的，后序序列：左右根。也就是说当从右往左获取值的时候，先获取的是根，然后是右子树，最后才是左子树。

图解

中序：2143
后序：2431

• 以下【】中的值指的是中序序列
• 通过从右向左获取节点值，得到后序序列中的1，通过该值在中序序列的位置可知：根节点【1】位置，左子树所在区间【2】，右子树所在区间【43】
  
• 接下来构造root=1的右子树，已知右子树所在区间【43】
• 通过从右向左获取节点值，得到后序序列中的3，通过该值在中序序列的位置可知：根节点【3】位置，左子树所在区间【4】
• 接下来构造root=3的右子树，【3】在【43】的右部分为空，因此中序序列中【3】的索引下标+1，一定造成left>right，返回null，即【3】的右子树为null
• 接下来构造root=3的左子树，已知左子树所在区间【4】
• 通过从右向左获取节点值，得到后序序列中的4，通过该值在中序序列的位置可知：根节点【4】位置，其没有左右子树，直接返回
  
• root=3的左右子树都已构造完成，可以返回了。
• root=1的右子树构造完成，现在构造左子树，已知左子树所在区间【2】
• 通过从右向左获取节点值，得到后序序列中的2，通过该值在中序序列的位置可知：根节点【2】位置，其没有左右子树，直接返回
• root=1的左右子树都已构造完成，可以返回了。

【前序、中序遍历序列】构造二叉树

/ * 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 { 
    int p_left; Map<Integer,Integer> map=new HashMap<>(); int[] preorder,inorder; public TreeNode buildTree(int[] preorder, int[] inorder) { 
    this.preorder=preorder; this.inorder=inorder; int idx=0; for(Integer val:inorder){ 
    map.put(val,idx++); } p_left=0; return helper(0,inorder.length-1); } //两个方法参数依旧是代表在中序序列的一个区间，该区间表示囊括了一棵子树的所有节点\ //区间内一定有一个是该树的根节点 //在根节点的左边部分区间【i_left,根节点索引-1】则是树下的左子树 //显而易见，其右边【根节点索引+1,i_right】则为该树的右子树 public TreeNode helper(int i_left,int i_right){ 
    if(i_left>i_right){ 
    return null; } int val=preorder[p_left]; TreeNode root=new TreeNode(val); int idx=map.get(val); p_left+=1; root.left=helper(i_left,idx-1); root.right=helper(idx+1,i_right); return root; } }