Leetcode 从中序与后序遍历序列构造二叉树
https://i-blog.csdnimg.cn/direct/4e643432ae184341b8fefa76dedfccbd.pngjava 递归实现
class Solution {
private HashMap<Integer, Integer> inorderIndexMap;
private int postorderIndex;
public TreeNode buildTree(int[] inorder, int[] postorder) {
inorderIndexMap = new HashMap<>();
postorderIndex = postorder.length - 1;
for(int i = 0; i < inorder.length; i++) {
inorderIndexMap.put(inorder, i);
}
return Helper(postorder, 0, inorder.length - 1);
}
private TreeNode Helper(int[] postorder, int inorderStart, int inorderEnd) {
if(inorderStart > inorderEnd) return null;
//首先确定根节点的值
int rootValue = postorder;
TreeNode root = new TreeNode(rootValue);
//获取根节点在中序遍历中的索引，用于后面划分左右子树
int inorderIndex = inorderIndexMap.get(rootValue);
// 递归构建右子树和左子树
// 注意：需要先构建右子树，因为后序遍历的顺序是左右根
root.right = Helper(postorder, inorderIndex + 1, inorderEnd);
root.left = Helper(postorder, inorderStart, inorderIndex - 1);
return root;
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]