赞
踩
给定两个整数数组 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 说明没有左孩子或右孩子,模拟一遍就明白了
- class Solution {
- public TreeNode buildTree(int[] inorder, int[] postorder) {
- if (inorder.length == 1) return new TreeNode(inorder[0]);
- Stack<Integer> postStack = new Stack<>();
- HashMap<Integer, Integer> inorderHash = new HashMap<>();
- for (int i = 0; i < inorder.length; i++) {
- postStack.push(postorder[i]);
- inorderHash.put(inorder[i], i);
- }
- TreeNode root = bdTree(0,inorder.length-1,inorderHash,postStack);
- return root;
- }
-
- public TreeNode bdTree(int left, int right,HashMap<Integer,Integer> inHash, Stack<Integer> postStack) {
- if (left == right) return new TreeNode(postStack.pop()); // 当前是叶子节点
- if (left > right) return null; // 当前节点无左孩子或右孩子
- int rootVal = postStack.pop();
- int rootIndex = inHash.get(rootVal);
- TreeNode root = new TreeNode(rootVal); // 根
- root.right = bdTree(rootIndex+1,right,inHash,postStack); // 右
- root.left = bdTree(left,rootIndex-1,inHash,postStack); // 左
- return root;
- }
- }

Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。