LeetCode 105. 从前序与中序遍历序列构造二叉树

2020-05-22 16:04:22来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

LeetCode 105. 从前序与中序遍历序列构造二叉树

我的LeetCode:https://leetcode-cn.com/u/ituring/

我的LeetCode刷题源码[GitHub]:https://github.com/izhoujie/Algorithmcii

LeetCode 105. 从前序与中序遍历序列构造二叉树

题目

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如,给出

前序遍历 preorder =?[3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树:


    3
   / \
  9  20
    /  \
   15   7

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

前序遍历:根左右
中序遍历:左根右

首先很容易得到前序遍历的首个元素就是树的根,若跟元素为root,那么:

  • 在中序遍历数组root元素的左侧部分就是树的左子树[0,R-1];
  • 在中序遍历数组root元素的右侧部分就是树的右子树[R+1,length];
    且:
  • 前序遍历的[1,R+1]是根的左子树;
  • 前序遍历的[R+2,length]是根的右子树;

根据以上分析是可以递归重建二叉树的;

思路1-分割数组对应到子树重建

根据上面的分析,分割数组,每次新建当前节点为上层的子节点,直至处理完数组;

算法复杂度:

  • 时间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $
  • 空间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $ 分割数组需要的空间

思路2-不分割数组,控制双指针移动构建

因为递归分割需要创建新数组,所以思路1是非常耗时的,如果直接对原数组元素处理不用新建数组将有很大的提速;

先序遍历的[0]在中序遍历里的位置若为i,那么i-1在顺序上是两个遍历处理的左子树的最后一个节点,i+1以及之后的节点就是右子树了;
那么可以以这个条件作为构建左子树完毕的退出条件,退出后继续构建右子树;
所以,记录双指针分别对应两个遍历,i-先序遍历,j-中序遍历:

  • [i]!=[j],递归构建左子树,i++;
  • [i]==[j],i++,j++,跳过根节点,开始递归构建右子树;
  • j==length构建完毕;

算法复杂度:

  • 时间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $
  • 空间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $ 递归栈的深度,最差时

算法源码示例

package leetcode;

import java.util.Arrays;

/**
 * @author ZhouJie
 * @date 2020年5月22日 下午1:28:22 
 * @Description: 105. 从前序与中序遍历序列构造二叉树
 *
 */
public class LeetCode_0105 {

}

//  Definition for a binary tree node.
class TreeNode_0105 {
	int val;
	TreeNode_0105 left;
	TreeNode_0105 right;

	TreeNode_0105(int x) {
		val = x;
	}
}

class Solution_0105 {
	/**
	 * @author: ZhouJie
	 * @date: 2020年5月22日 下午1:29:25 
	 * @param: @param preorder
	 * @param: @param inorder
	 * @param: @return
	 * @return: TreeNode_0105
	 * @Description: 1-分割数组对应到子树递归处理;
	 *
	 */
	public TreeNode_0105 buildTree_1(int[] preorder, int[] inorder) {
		if (preorder.length == 0 || inorder.length == 0) {
			return null;
		} else {
			TreeNode_0105 root = new TreeNode_0105(preorder[0]);
			for (int i = 0; i < inorder.length; i++) {
				if (preorder[0] == inorder[i]) {
					root.left = buildTree_1(Arrays.copyOfRange(preorder, 1, i + 1), Arrays.copyOfRange(inorder, 0, i));
					root.right = buildTree_1(Arrays.copyOfRange(preorder, i + 1, preorder.length),
							Arrays.copyOfRange(inorder, i + 1, inorder.length));
					break;
				}
			}
			return root;
		}
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020年5月22日 下午2:02:20 
	 * @param: @param preorder
	 * @param: @param inorder
	 * @param: @return
	 * @return: TreeNode_0105
	 * @Description: 2-直接在数组上递归,不分割数组,效率高;
	 *
	 */
	private int indexPreorder = 0;
	private int indexInorder = 0;

	public TreeNode_0105 buildTree_2(int[] preorder, int[] inorder) {
		return buildHelper(preorder, inorder, null);
	}

	private TreeNode_0105 buildHelper(int[] preorder, int[] inorder, TreeNode_0105 node) {
		if (node != null && node.val == inorder[indexInorder] || indexInorder == preorder.length) {
			return null;
		}
		// 开始构建左子树
		TreeNode_0105 root = new TreeNode_0105(preorder[indexPreorder]);
		// 先从preorder开始处理,当处理到等于inorder[0]的节点时,表明根的左子树已经构建完成,可以开始递归构建根的右子树了
		if (preorder[indexPreorder] == inorder[indexInorder]) {
			indexPreorder++;
			indexInorder++;
		} else {
			indexPreorder++;
			root.left = buildHelper(preorder, inorder, root);
			indexInorder++;
		}
		// 对于根而言,开始右子树的递归构建
		root.right = buildHelper(preorder, inorder, node);
		return root;
	}
}


原文链接:https://www.cnblogs.com/izhoujie/p/12937442.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:java.lang.String 的 + 号操作到底做了什么?

下一篇:RedisTemplate实现消息队列并且批量插入数据。