Leetcode 思路-105.从前序与中序序列构造二叉树

105.从前序与中序序列构造二叉树给定两个整数数组preorder和inorder其中preorder是二叉树的先序遍历inorder是同一棵树的中序遍历请构造二叉树并返回其根节点。1.简单思路根据先序遍历根节点在前的特点取到根节点后将中序遍历分为左子树和右子树两部分递归构建二叉树哈希表存储中序遍历以便于能根据节点值取下标构建函数public TreeNode myBuildTree(int[] preorder, int[] inorder,int pre_L,int pre_R,int in_L,int in_R)2.迭代思路建立栈用来存储当前节点还未遍历过右子树的父节点、初始化存储先序遍历的第一个节点建立指针用来定位中序遍历序列初始化指向inOrder[0]从先序遍历序列第二个节点开始遍历先序遍历序列如果栈顶元素node和当前指针指向的中序遍历节点inNow不一致证明栈顶元素必有左子树并且其左儿子必然是当前先序遍历的节点给栈顶元素构建左儿子并将其左儿子入栈如果node和inNow一致证明栈顶节点没有左子树,那么inNow必然是栈中某一节点的右儿子此时栈中节点和中序遍历部分序列一定相反那么给指向中序遍历序列的指针1并弹出栈中一个节点直到指针指向的节点和node不同或者栈空此时弹出的元素的右儿子即为inNow构建二叉树并将inNow入栈if(preorder null || preorder.length 0){ return null; } TreeNode root new TreeNode(preorder[0]); //建立栈用来存储当前节点还未遍历过右子树的父节点 DequeTreeNode stack new LinkedListTreeNode(); stack.push(root); //建立指针用来遍历中序遍历序列 int p 0; // for (int i 1; i preorder.length; i) { //如果栈顶元素和当前指针指向的中序遍历节点不一致证明栈顶元素必有左子树并且其左儿子必然是当前先序遍历的节点 //给栈顶元素构建左儿子并将其左儿子入栈 TreeNode node stack.peek(); int inNow preorder[i]; if(node.val ! inorder[p]){ TreeNode left new TreeNode(inNow); node.left left; stack.push(left); } /*如果栈顶元素node和当前指针指向的中序遍历节点inNow一致证明栈顶节点没有左子树, 那么当前先序遍历的节点inNow必然是栈中某一节点的右儿子此时栈中节点和中序遍历部分序列一定相反 那么给指向中序遍历序列的指针1并弹出栈中一个节点直到指针指向的节点和栈顶节点不同或者栈空 此时弹出的元素的右儿子即为inNow构建二叉树并将inNow入栈 */ else{ while (!stack.isEmpty() stack.peek().valinorder[p]){ node stack.poll(); p; } node.right new TreeNode(inNow); stack.push(node.right); } } return root;