【LeetCode】 39 从中序与后序遍历序列构造二叉树

题目:

image-20200618000925773

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如,给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树:

    3
   / \
  9  20
    /  \
   15   7

思路:

我看了官方的解析懂了。但是自己的话太难概括,下次刷到这题 再去看吧

https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/solution/cong-zhong-xu-yu-hou-xu-bian-li-xu-lie-gou-zao-e-5/

代码:

class Solution {
  int post_idx;
  int[] postorder;
  int[] inorder;
  HashMap<Integer, Integer> idx_map = new HashMap<Integer, Integer>();

  public TreeNode helper(int in_left, int in_right) {
    //如果没有元素 返回null
    if (in_left > in_right)
      return null;

    //将post_idx元素(后序遍历的最后一个元素)作为根元素
    int root_val = postorder[post_idx];
    TreeNode root = new TreeNode(root_val);

    //根分割顺序列表
	//变成左右子树
    int index = idx_map.get(root_val);

    // 递归
    post_idx--;
    // 构建右子树
    root.right = helper(index + 1, in_right);
    // 构建左子树
    root.left = helper(in_left, index - 1);
    return root;
  }

  public TreeNode buildTree(int[] inorder, int[] postorder) {
    this.postorder = postorder;
    this.inorder = inorder;
    //从最后一个postorder元素开始
    post_idx = postorder.length - 1;

    //建立一个hashmap值-&gt;其索引
    int idx = 0;
    for (Integer val : inorder)
      idx_map.put(val, idx++);
    return helper(0, inorder.length - 1);
  }
}
# 面试题 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×