1. 首页
  2. Leetcode经典148题

leetcode-106-Construct-Binary-Tree-from-Inorder-and-Postorder-Traversal

题目描述(中等难度)

leetcode-106-Construct-Binary-Tree-from-Inorder-and-Postorder-Traversal

根据二叉树的中序遍历和后序遍历还原二叉树。

思路分析

可以先看一下 public TreeNode buildTree(int[] inorder, int[] postorder) { HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < inorder.length; i++) { map.put(inorder[i], i); } return buildTreeHelper(inorder, 0, inorder.length, postorder, 0, postorder.length, map); } private TreeNode buildTreeHelper(int[] inorder, int i_start, int i_end, int[] postorder, int p_start, int p_end, HashMap<Integer, Integer> map) { if (p_start == p_end) { return null; } int root_val = postorder[p_end - 1]; TreeNode root = new TreeNode(root_val); int i_root_index = map.get(root_val); int leftNum = i_root_index - i_start; root.left = buildTreeHelper(inorder, i_start, i_root_index, postorder, p_start, p_start + leftNum, map); root.right = buildTreeHelper(inorder, i_root_index + 1, i_end, postorder, p_start + leftNum, p_end - 1, map); return root; }

解法二 stop 值

这里的话,之前说了,递归的话得先构造右子树再构造左子树,此外各种指针,也应该从末尾向零走。

视线从右往左看。

    3
   / \
  9  20
    /  \
   15   7

s 初始化一个树中所有的数字都不会相等的数,所以代码中用了一个 long 来表示
<------------------
中序
  9, 3, 15, 20, 7
^               ^
s               i

后序
9, 15, 7, 20, 3
              ^  
              p
<-------------------

pi 都从右往左进行遍历,所以 p 开始产生的每次都是右子树的根节点。之前代码里的++要相应的改成--

int post;
int in; 
public TreeNode buildTree(int[] inorder, int[] postorder) {
    post = postorder.length - 1;
    in = inorder.length - 1;
    return buildTreeHelper(inorder, postorder, (long) Integer.MIN_VALUE - 1);
}

private TreeNode buildTreeHelper(int[] inorder, int[] postorder, long stop) {
    if (post == -1) {
        return null;
    }
    if (inorder[in] == stop) {
        in--;
        return null;
    }
    int root_val = postorder[post--];
    TreeNode root = new TreeNode(root_val);
    root.right = buildTreeHelper(inorder, postorder, root_val);
    root.left = buildTreeHelper(inorder, postorder, stop);
    return root;
}

解法三 栈

之前解法是构造左子树、左子树、左子树,出现相等,构造一颗右子树。这里相应的要改成构造右子树、右子树、右子树,出现相等,构造一颗左子树。和解法二一样,两个指针的话也是从末尾到头部进行。

public TreeNode buildTree(int[] inorder, int[] postorder) {
    if (postorder.length == 0) {
        return null;
    }
    Stack<TreeNode> roots = new Stack<TreeNode>();
    int post = postorder.length - 1;
    int in = inorder.length - 1;
    TreeNode curRoot = new TreeNode(postorder[post]);
    TreeNode root = curRoot;
    roots.push(curRoot);
    post--;
    while (post >=  0) {
        if (curRoot.val == inorder[in]) {
            while (!roots.isEmpty() && roots.peek().val == inorder[in]) {
                curRoot = roots.peek();
                roots.pop();
                in--;
            }
            curRoot.left = new TreeNode(postorder[post]);
            curRoot = curRoot.left;
            roots.push(curRoot);
            post--;
        } else {
            curRoot.right = new TreeNode(postorder[post]);
            curRoot = curRoot.right;
            roots.push(curRoot);
            post--;
        }
    }
    return root;
}

理解了

阅读全文

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「方志朋」,公众号后台回复「666」 免费领取我精心整理的进阶资源教程
  4. JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

    本文著作权归作者所有,如若转载,请注明出处

    转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

    标题:leetcode-106-Construct-Binary-Tree-from-Inorder-and-Postorder-Traversal

    链接:https://www.javajike.com/article/3243.html

« leetcode-105-Construct-Binary-Tree-from-Preorder-and-Inorder-Traversal
leetcode-107-Binary-Tree-Level-Order-TraversalII»

相关推荐

QR code