前序排序和中序排列
前序和中序结合，具有哪些特点
通过上面的排序，可以发现，前序排列的第一个节点A一定是父节点,前序排列的第二个节点B一定第一个节点A的左节点。
知道了父节点和左节点，还需要知道其右节点，那么右节点是怎么获取的呢？可以看下面张图。
想要找到右节点的话，得需要先确定前序遍历中的左子树和右子树的范围,右子树的第一个元素就是其右节点。
寻找右节点
定义前序排列的左下标为preLeft,右下标为preRight,中序排列的左下标为inLeft,右下标为inRIght。
可以先使用HashMap遍历中序存储每个节点在中序中的下标。通过HashMap获取到preLeft节点在中序的下标pIndex,因为中序中的左子树长度和前序中的左子树一定是相同的，因此我们可以算出，前序遍历中的左子树的结束下标x
pIndex - inLeft = x - preLeft
x = pIndex - inLeft + preLeft
算出前序遍历中左子树结束下标为pIndex - inLeft + preLeft,右子数的开始下标为pIndex - inLeft + preLeft+1
上面图中给出了，前序和中序排列中所需的所有下标了，可以发现，这是一个循环的过程，所以可以使用递归来实现
代码实现
/**
* 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 {
HashMap<Integer,Integer> cacheIndex;
public TreeNode buildTree(int[] preorder, int[] inorder) {
cacheIndex = new HashMap<>();
//先遍历中序存储 节点=>下标
for (int i=0;i<inorder.length;i++){
cacheIndex.put(inorder[i],i);
}
return dfs(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
}
/**
* @param preorder
* @param preLeft 前序遍历的第一个下标
* @param preRight 前序遍历的最后一个下标
* @param inorder
* @param inLeft 中序遍历的第一个下标
* @param inRight 中序遍历的最后一个下标
* @return
*/
public TreeNode dfs(int[] preorder,int preLeft,int preRight,int[] inorder,int inLeft,int inRight){
//注意：这里一定是判断>,而不是>=。可以举个例子当节点中只有一个节点时preLeft = preRight的，它的左节点和右节点是存在的，都是Null
if(preLeft>preRight || inLeft>inRight){
return null;
}
//实例化前序遍历的第一个节点
TreeNode root = new TreeNode(preorder[preLeft]);
//通过hashMap获取到第一个节点在中序遍历中的下标
int pivot = cacheIndex.get(preorder[preLeft]);
//上边解释了，前序数组的左子树的第一个元素是其左节点，
//所以前序列表中的左子树为preLeft+1 -> pivot-inLeft+preLeft,中序列表的左子树为inLeft->pivot-1
root.left = dfs(preorder,preLeft+1,pivot-inLeft+preLeft,inorder,inLeft,pivot-1);
//上面也介绍了，在前序数组中的右子树的第一个节点是其右节点
//所以前序列表中的右子树为pivot-inLeft+preLeft+1 -> preRight,中序列表中的右子树为pivot+1 -> inRight
root.right = dfs(preorder,pivot-inLeft+preLeft+1,preRight,inorder,pivot+1,inRight);
return root;
}
}
如果还是没看懂的话，可以看该[leedcode官方视频]。(https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solutions/255811/cong-qian-xu-yu-zhong-xu-bian-li-xu-lie-gou-zao-9/)
网友评论