先序遍历和中序遍历
1、先序遍历的结果中第一个元素一定是根节点
2、先序遍历结果= 根节点+左子树先序结构+右子树先序结果
3、中序遍历结果= 左子树的中序结果+根节点+右子树的中序结果
根据上图,3为根节点,根据中序遍历9是3的左子树而且只有一个节点,先序中9后面的20就是3的右子树的根节点,然后再看中序遍历,15在20的左侧7在20右侧,得15是20的左子树7是20的右子树。最后构建出的树如下图:
代码思路:
注:中序遍历数组中根节点的左边都是左子树的节点,根节点右边都是右子树节点
1、设置变量inedx 方便从preorder数组中从0号下标开始获取节点。
2、判断inedx的合法性,防止我们在最终的递归途中数组越界异常。
3、中序遍历中根结点可以作为一道分界线,左边是他的左子树结点,右边是右子树结点,所以一开始的inorderLeft 为0 而inorderRight为中序遍历数组的长度。
4、根结点就是先序遍历的第一个结点,构建根结点,然后index++(方法中index只加一次是因为在preorder数组中index下标的元素只可能是左结点或者右结点)
5、构建根结点的左子树,(在此之前我们要在中序遍历中找到根结点元素的下标pos),我们知道 中序遍历的序列组成可以表示为 :左子树结点+根结点+右子树结点 所以,根结点的左结点一定在pos之前。
6、然后我们进行递归进行判断inorderLeft 和inorderRight(就是上一个方法传来的pos值)的合法性,只要inorderLeft不是大于等于inorderRight 就说明在根结点下标的左边有元素,也就是说根结点的左子树不为空。
7、构建该结点然后再次进行递归判断,直到根结点的左子树的根结点建立完。此时就要建立根节点的子树、此时传入的inorderLeft为pos+1和一开始的inorderRight,然后进行递归处理,只要 inorderLeft不是大于等于inorderRight 就说明在根结点下标的右边有元素,也就是说明有右子树,之后进行构建。
//preorder这个数组和inorder长度相同
//用index记录访问到哪个节点,记录在preorder中访问到哪个元素
private int index = 0;
public TreeNode buildTree(int[] preorder, int[] inorder){
index = 0;
//借助buildTreeHelper方法进行递归
//加入一对参数表示当前子树对应的中序遍历结果的区间。
return buildTreeHelper(preorder,inorder,0,inorder.length);
}
//[inorderLeft,inorderRight)表示当前这个子树的中序遍历区间
private TreeNode buildTreeHelper(int[] preorder, int[] inorder, int inorderLeft, int inorderRight) {
if(inorderLeft >= inorderRight){
//中序遍历区间为空,当前子树为空树
return null;
}
if(index >= preorder.length){
//先序中的所有元素都访完毕
return null;
}
//根据index取出当前树的根节点的值,并构造根节点
TreeNode newNode = new TreeNode(preorder[index]);
//知道根节点后,需要根据根节点,在中序遍历结果中找到左右子树的范围
//找出当前节点在中序结果中的位置,位置确定,左右子树位置就确定了
//左子树对应的中序区间[inorderLeft,pos)
//右子树对应的中序区间[pos+1,inorderRight)
int pos = find(inorder,inorderLeft,inorderRight,newNode.val);//在中序遍历中找到节点的下标
index++;//只++一次
newNode.left = buildTreeHelper(preorder,inorder,inorderLeft,pos);
newNode.right = buildTreeHelper(preorder,inorder,pos+1,inorderRight);
return newNode;
}
private int find(int[] inorder, int inorderLeft, int inorderRight, int val) {
for(int i = inorderLeft;i < inorderRight; i++){
if(inorder[i] == val){
return i;
}
}
return -1;
}
后序遍历和中序遍历
1、后序遍历的结果中最后个元素一定是根节点
2、后序遍历结果= 左子树后序结构+根节点+右子树后序结果
3、中序遍历结果= 左子树的中序结果+根节点+右子树的中序结果
后序遍历为9-》15-》7-》20-》3
后序遍历结果倒置3-》20-》7-》15-》9 相当于一个“镜像”先序,先根节点再右子树再左子树
所以先对后序遍历的数组逆序,之后对上述的代码进行修改先进行右子树再进行左子树即可。
private int index = 0;
public TreeNode buildTree(int[] inorder, int[] posorder){
index = 0;
int[] posorder1 = new int[posorder.length];
for(int i = 0; i < posorder.length; i++){
posorder1[i] = posorder[posorder.length-i-1];
}
return buildTreeHelper(posorder1,inorder,0,inorder.length);
}
private TreeNode buildTreeHelper(int[] posorder1, int[] inorder, int inorderLeft, int inorderRight) {
if(inorderLeft >= inorderRight){
return null;
}
if(index >= posorder1.length){
return null;
}
TreeNode newNode = new TreeNode(posorder1[index]);
int pos = find(inorder,inorderLeft,inorderRight,newNode.val);
index++;//只++一次
newNode.right = buildTreeHelper(posorder1,inorder,pos+1,inorderRight);
newNode.left = buildTreeHelper(posorder1,inorder,inorderLeft,pos);
return newNode;
}
private int find(int[] inorder, int inorderLeft, int inorderRight, int val) {
for(int i = inorderLeft;i < inorderRight; i++){
if(inorder[i] == val){
return i;
}
}
return -1;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/152997.html