2024.2.21力扣每日一题——从中序和后序遍历序列构建二叉树

本文主要是介绍2024.2.21力扣每日一题——从中序和后序遍历序列构建二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2024.2.21

- - 题目来源
  - 我的题解
  - - 方法一递归方式
    - 方法二迭代方式

题目来源

力扣每日一题；题序：106

我的题解

方法一递归方式

后序特点：[ [左子树的前序遍历结果], [右子树的前序遍历结果]，根节点 ]
中序特点：[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
发现后序遍历的数组最后一个元素代表的即为根节点。知道这个性质后，我们可以利用已知的根节点信息在中序遍历的数组中找到根节点所在的下标，然后根据其将中序遍历的数组分成左右两部分，左边部分即左子树，右边部分为右子树，针对每个部分可以用同样的方法继续递归下去构造。
时间复杂度：O( $n^2$ )
空间复杂度：O(n)

public TreeNode buildTree(int[] inorder, int[] postorder) {return createTree(inorder,postorder,0,inorder.length-1,0,postorder.length-1);
}
public TreeNode createTree(int[] inorder, int[] postorder,int iL,int iR,int pL,int mid){if(iL>iR||pL>mid)return null;int val=postorder[mid];TreeNode root=new TreeNode(val);int index=find(inorder,val,iL,iR);int left=index-iL;int right=iR-index;root.left=createTree(inorder,postorder,iL,index-1,pL,mid-right-1);root.right=createTree(inorder,postorder,index+1,iR,mid-right,mid-1);return root;
}public int find(int[] inorder,int val,int iL,int iR){int index=iL;for(int i=iL;i<=iR;i++){if(inorder[i]==val){index=i;}}return index;
}

在中序遍历中对根节点进行定位时，需要频繁扫描整个中序遍历的结果并找出根节点，时间复杂度较高。可以考虑使用哈希表来帮助快速地定位根节点。在此后构造二叉树的过程中，就只需要 O(1)的时间对根节点进行定位了。

//使用哈希表优化
public TreeNode buildTree(int[] inorder, int[] postorder) {Map<Integer,Integer> map=new HashMap<>();for(int i=0;i<inorder.length;i++){map.put(inorder[i],i);}return createTree(inorder,postorder,0,inorder.length-1,0,postorder.length-1,map);
}
public TreeNode createTree(int[] inorder, int[] postorder,int iL,int iR,int pL,int mid,Map<Integer,Integer> map){if(iL>iR||pL>mid)return null;int val=postorder[mid];TreeNode root=new TreeNode(val);int index=map.get(val);int left=index-iL;int right=iR-index;root.left=createTree(inorder,postorder,iL,index-1,pL,mid-right-1,map);root.right=createTree(inorder,postorder,index+1,iR,mid-right,mid-1,map);return root;
}