本文共 2498 字,大约阅读时间需要 8 分钟。
我们知道,中序遍历是左子树->根节点->右子树。因此我们可以通过中序遍历可以确定左右子树的元素个数。
而通过前序(后序)遍历,我们可以确定根节点的位置,然后通过寻找根节点在中序遍历的位置,可以确定左右子树。
然后递归递归左右子树实现构建二叉树。
前序和中序:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { if(preorder==null&&inorder==null) return null; return rebuild (preorder,inorder,0,preorder.length-1,0,inorder.length-1); } private TreeNode rebuild(int[] preorder, int[] inorder,int preleft,int preright,int inleft,int inright) { if(preleft>preright||inleft>inright) return null; TreeNode t=new TreeNode(preorder[preleft]); t.left=t.right=null; int loc=0; //寻找节点在中序遍历中的位置 for (int i=inleft;i<=inright;i++) if(inorder[i]==preorder[preleft]) { loc=i; break; } //preleft+1表示该节点的左孩子的位置,preleft+loc-inleft表示该节点左子树的末尾 t.left=rebuild (preorder,inorder,preleft+1,preleft+loc-inleft,inleft,loc-1); //preleft+loc-inleft+1表示该节点的右孩子的位置,preright表示该节点右子树的末尾 t.right=rebuild (preorder,inorder,preleft+loc-inleft+1,preright,loc+1,inright); return t; }}
后序和中序:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { if(inorder==null&&postorder==null) return null; return rebuild (inorder,postorder,0,postorder.length-1,0,inorder.length-1); } private TreeNode rebuild(int[] in, int[] post,int postleft,int postright,int inleft,int inright) { if(postleft>postright||inleft>inright) return null; int loc=-1; TreeNode t=new TreeNode(post[postright]); t.left=t.right=null; for (int i=inleft;i<=inright;i++) if(in[i]==post[postright]) { loc=i; break; } //postright-inright+loc-1表示该节点左孩子的位置,posleft表示左子树的起始 t.left=rebuild (in,post,postleft,postright-inright+loc-1,inleft,loc-1); //postright-1表示该节点右孩子的位置,postright-inright+loc表示右子树的起始 t.right=rebuild(in,post,postright-inright+loc,postright-1,loc+1,inright); return t; }}
转载地址:http://jvaen.baihongyu.com/