抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

重建二叉树

题:输入某二叉树的前序和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如,输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建并输出头结点,二叉树定义如下:

class TreeNode {
int val;
TreeNode left;
TreeNode right;
}

解法:递归,原理如下图:想的是否想简单一点,然后再用递归思想处理

代码:

/**
* 递归重构二叉树
*
@param pre 先序遍历
*
@param in 中序遍历
*
@return 完成后的新二叉树
*/
public static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
return constructCore(pre, 0, pre.length - 1, in, 0, in.length - 1);
}

/**
* 递归主要逻辑
*
@param pre 先序遍历
*
@param startPreOrder 先序遍历起始点
*
@param endPreOrder 先序遍历终点
*
@param in 中序遍历
*
@param startInOrder 中序遍历起始点
*
@param endInOrder 中序遍历终点
*
@return 当前重构后的节点
*/
private static TreeNode constructCore(int[] pre, int startPreOrder, int endPreOrder, int[] in, int startInOrder, int endInOrder) {
//前序遍历的起点是根节点的值
int rootValue = pre[startPreOrder];
TreeNode root = new TreeNode();
root.val = rootValue;
root.left = root.right = null;
//如果只有一个节点
if (startPreOrder == endPreOrder) {
if (startInOrder == endInOrder && pre[startPreOrder] == in[startInOrder]) {
//中序遍历起始位置等于结尾位置 并且这两个位置的值相等
return root;
} else {
//否则不合法 返回null
return null;
}
}
//在中序遍历中找到根节点的值 rootInOrder为中序遍历中根节点的位置
int rootInOrder = startInOrder;
while (rootInOrder <= endInOrder && in[rootInOrder] != rootValue) {
++rootInOrder;
}
if (rootInOrder == endInOrder && in[rootInOrder] != rootValue) {
//中序遍历头尾位置相同 且找到的根节点值与根节点不一致 则认为不合法 返回null
return null;
}

int leftLength = rootInOrder - startInOrder;
int leftPreOrderEnd = startPreOrder + leftLength;

if (leftLength > 0) {
//构建左子树
root.left = constructCore(pre, startPreOrder + 1, leftPreOrderEnd, in, startInOrder, rootInOrder - 1);
}
if (leftLength < endPreOrder - startPreOrder) {
//构建右子树
root.right = constructCore(pre, leftPreOrderEnd + 1, endPreOrder, in, rootInOrder + 1, endInOrder);
}
return root;
}

测试主函数加递归输出新二叉树的先序遍历 :

public static void main(String[] args) {
int[] pre = {1, 2, 4, 7, 3, 5, 6, 8};
int[] in = {4, 7, 2, 1, 5, 3, 8, 6};
preOrderTraverse(reConstructBinaryTree(pre, in));
}

/**
* 递归先序遍历
*
@param root root节点
*/
public static void preOrderTraverse(TreeNode root) {
if (root != null) {
System.out.print(root.val + " ");
preOrderTraverse(root.left);
preOrderTraverse(root.right);
}
}

但是书中表达的判断逻辑还是有点多,不方便快速记忆和理解,可解除一些限定范围:

    private static TreeNode constructCore(int[] pre, int startPreOrder, int endPreOrder, int[] in, int startInOrder, int endInOrder) {
if (startPreOrder>endPreOrder||startInOrder>endInOrder){
return null;
}
//前序遍历的起点是根节点的值
int rootValue = pre[startPreOrder];
TreeNode root = new TreeNode();
root.val = rootValue;
// root.left = root.right = null;
//如果只有一个节点
// if (startPreOrder == endPreOrder) {
// if (startInOrder == endInOrder && pre[startPreOrder] == in[startInOrder]) {
//中序遍历起始位置等于结尾位置 并且这两个位置的值相等
// return root;
// } else {
//否则不合法 返回null
// return null;
// }
// }
//在中序遍历中找到根节点的值 rootInOrder为中序遍历中根节点的位置
int rootInOrder = startInOrder;
while (rootInOrder <= endInOrder && in[rootInOrder] != rootValue) {
++rootInOrder;
}
// if (rootInOrder == endInOrder && in[rootInOrder] != rootValue) {
//中序遍历头尾位置相同 且找到的根节点值与根节点不一致 则认为不合法 返回null
// return null;
// }

int leftLength = rootInOrder - startInOrder;
int leftPreOrderEnd = startPreOrder + leftLength;

// if (leftLength > 0) {
//构建左子树
root.left = constructCore(pre, startPreOrder + 1, leftPreOrderEnd, in, startInOrder, rootInOrder - 1);
// }
// if (leftLength < endPreOrder - startPreOrder) {
//构建右子树
root.right = constructCore(pre, leftPreOrderEnd + 1, endPreOrder, in, rootInOrder + 1, endInOrder);
// }
return root;
}

最终精简版:

private static TreeNode constructCore(int[] pre, int startPreOrder, int endPreOrder, int[] in, int startInOrder, int endInOrder) {
if (startPreOrder > endPreOrder || startInOrder > endInOrder) {
return null;
}
//前序遍历的起点是根节点的值
int rootValue = pre[startPreOrder];
TreeNode root = new TreeNode();
root.val = rootValue;

//在中序遍历中找到根节点的值 rootInOrder为中序遍历中根节点的位置
int rootInOrder = startInOrder;
while (rootInOrder <= endInOrder && in[rootInOrder] != rootValue) {
++rootInOrder;
}

int leftLength = rootInOrder - startInOrder;
int leftPreOrderEnd = startPreOrder + leftLength;

//构建左子树
root.left = constructCore(pre, startPreOrder + 1, leftPreOrderEnd, in, startInOrder, rootInOrder - 1);
//构建右子树
root.right = constructCore(pre, leftPreOrderEnd + 1, endPreOrder, in, rootInOrder + 1, endInOrder);
return root;
}

以上,应该还是比较好理解的。


0条评论

发表评论