当前位置:   article > 正文

java - 106. 从中序与后序遍历序列构造二叉树 - 递归_给定两个整数数组inorder和postorder,其中inorder是二叉树的中序遍历,posto

给定两个整数数组inorder和postorder,其中inorder是二叉树的中序遍历,postorder是

一、题目

给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。

输入:inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出:[3,9,20,null,null,15,7]

二、思路

1 每次从postorder中拿到当前数组尾部的数(这里我们用一个栈来实现),作为当前树的根。
2 然后在inorder中找到该数的索引(用hashmap来实现),其右边作为右子树,左边作为左子树(注意这个顺序,后续的倒序一定是根右左)
3 注意一些特殊情况,我们用left和right来判断:

        当left==right,说明走到同一节点了,无左右孩子,为叶子节点直接返回该节点;

        当left > right 说明没有左孩子或右孩子,模拟一遍就明白了

三、代码

  1. class Solution {
  2. public TreeNode buildTree(int[] inorder, int[] postorder) {
  3. if (inorder.length == 1) return new TreeNode(inorder[0]);
  4. Stack<Integer> postStack = new Stack<>();
  5. HashMap<Integer, Integer> inorderHash = new HashMap<>();
  6. for (int i = 0; i < inorder.length; i++) {
  7. postStack.push(postorder[i]);
  8. inorderHash.put(inorder[i], i);
  9. }
  10. TreeNode root = bdTree(0,inorder.length-1,inorderHash,postStack);
  11. return root;
  12. }
  13. public TreeNode bdTree(int left, int right,HashMap<Integer,Integer> inHash, Stack<Integer> postStack) {
  14. if (left == right) return new TreeNode(postStack.pop()); // 当前是叶子节点
  15. if (left > right) return null; // 当前节点无左孩子或右孩子
  16. int rootVal = postStack.pop();
  17. int rootIndex = inHash.get(rootVal);
  18. TreeNode root = new TreeNode(rootVal); // 根
  19. root.right = bdTree(rootIndex+1,right,inHash,postStack); // 右
  20. root.left = bdTree(left,rootIndex-1,inHash,postStack); // 左
  21. return root;
  22. }
  23. }
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/806293?site
推荐阅读
相关标签
  

闽ICP备14008679号