网站案例演示,wordpress外国模板,wordpress站群 会员,深圳室内设计培训106. 从中序与后序遍历序列构造二叉树
用分治思想#xff0c;后序遍历是左右中#xff0c;中序遍历是左中右#xff0c;后序遍历的最后一个元素就是根节点#xff0c;
在中序遍历中找到它的位置#xff0c;它前面的为左子树#xff0c;后面的为右子树#xff0c;并能计…106. 从中序与后序遍历序列构造二叉树
用分治思想后序遍历是左右中中序遍历是左中右后序遍历的最后一个元素就是根节点
在中序遍历中找到它的位置它前面的为左子树后面的为右子树并能计算左右子树结点个数算下标差即可然后递归算每一棵子树当成一棵树来处理中序遍历对应前几个结点与后序遍历前几个结点为一棵树上的结点。
/*** 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 {HashMapInteger,Integer mnew HashMap();int[] post;public TreeNode buildTree(int[] inorder, int[] postorder) {
for(int i0;iinorder.length;i)
{m.put(inorder[i],i);
}postpostorder;return tree(0,inorder.length-1,0,postorder.length-1);}TreeNode tree (int inbegin,int inend,int pbegin ,int pend){if(inbegininend||pbeginpend)return null;TreeNode curnew TreeNode(post[pend]);int idxm.get(post[pend]);cur.lefttree(inbegin,idx-1,pbegin,pbeginidx-inbegin-1);cur.righttree(idx1,inend,pbeginidx-inbegin,pend-1);return cur;}
}
105. 从前序与中序遍历序列构造二叉树
类似
/*** 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 {HashMapInteger,Integer m new HashMap();int[] pre;public TreeNode buildTree(int[] preorder, int[] inorder) {for(int i0;iinorder.length;i)m.put(inorder[i],i);prepreorder;return traval(0,inorder.length-1,0,preorder.length-1);}TreeNode traval(int inbegin,int inend,int pbegin,int pend)
{if (inbegininend||pbeginpend)return null;TreeNode curnew TreeNode(pre[pbegin]);int idxm.get(pre[pbegin]);cur.lefttraval(inbegin,idx-1,pbegin1,pbeginidx-inbegin);cur.righttraval(idx1,inend,pbeginidx-inbegin1,pend);return cur;
}
}
