从中序与后序遍历序列构造二叉树

简介: 从中序与后序遍历序列构造二叉树

/**

  • 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 {

Map<Integer, Integer> hm = new HashMap<>();

public TreeNode buildTree(int[] inorder, int[] postorder) {
    for (int i = 0; i < inorder.length; ++i) {
        hm.put(inorder[i], i);
    }
    return dfs(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
}

TreeNode dfs(int[] in, int il, int ir, int[] post, int pl, int pr) {
    if (il > ir) {
        return null;
    }
    int k = hm.get(post[pr]);
    TreeNode node = new TreeNode(post[pr]);
    node.left = dfs(in, il, k - 1, post, pl, pl + k - 1 - il);
    node.right = dfs(in, k + 1, ir, post, pl + k - il, pr - 1);
    return node;
}
AI 代码解读

}

目录
打赏
0
0
0
0
4
分享
相关文章
106_从中序与后序遍历序列构造二叉树
106_从中序与后序遍历序列构造二叉树
113 0
从中序与后序遍历序列构造二叉树
【10月更文挑战第13天】这段内容介绍了一种基于中序和后序遍历序列构建二叉树的方法。通过识别后序遍历中的根节点,并利用中序遍历划分左右子树,进而递归构建整棵树。文中提供了具体示例及Python代码实现,并分析了该方法的时间与空间复杂度。
149 0
21_从中序与后序遍历序列构造二叉树
21_从中序与后序遍历序列构造二叉树
从中序与后序遍历序列构造二叉树(C++实现)
从中序与后序遍历序列构造二叉树(C++实现)
95 1
|
9月前
|
leetcode-106:从中序与后序遍历序列构造二叉树
leetcode-106:从中序与后序遍历序列构造二叉树
64 0
从前序与中序遍历序列构造二叉树(C++实现)
从前序与中序遍历序列构造二叉树(C++实现)
113 1
105_从前序与中序遍历序列构造二叉树
105_从前序与中序遍历序列构造二叉树
105 0

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等