# 105. 從前序與中序遍歷序列構造二叉樹 ## 題目地址(105. 從前序與中序遍歷序列構造二叉樹) <https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/> ## 題目描述 ``` <pre class="calibre18">``` 根據一棵樹的前序遍歷與中序遍歷構造二叉樹。 注意: 你可以假設樹中沒有重復的元素。 例如，給出 前序遍歷 preorder = [3,9,20,15,7] 中序遍歷 inorder = [9,3,15,20,7] 返回如下的二叉樹： 3 / \ 9 20 / \ 15 7 ``` ``` ## 前置知識 - 二叉樹 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 目標是構造二叉樹。 構造二叉樹需要根的值、左子樹和右子樹。 此問題可被抽象為：從前序遍歷和中序遍歷中找到根節點、左子樹和右子樹。 先找根： 由前序遍歷的性質，第`0`個節點為當前樹的根節點。 再找左右子樹： 在中序遍歷中找到這個根節點，設其下標為`i`。由中序遍歷的性質，`0 ~ i-1` 是左子樹的中序遍歷，`i+1 ~ inorder.length-1`是右子樹的中序遍歷。 然后遞歸求解，終止條件是左右子樹為`null`。 We are going to construct a binary tree from its preorder and inorder traversal. To build a binary tree, it requires us to creact a new `TreeNode` as the root with filling in the root value. And then, find its left child and right child recursively until the left or right child is `null`. Now this problem is abstracted as how to find the root node, left child and right child from the preorder traversal and inorder traversal. In preorder traversal, the first node (`preorder[0]`) is the root of current binary tree. In inorder traversal, find the location of this root which is `i`. The left sub-tree is `0 to i-1` and the right sub-tree is `i+1 to inorder.length-1` in inorder traversal. Then applying the previous operation to the left and right sub-trees. ## 關鍵解析/Key Points 如何在前序遍歷的數組里找到左右子樹的： - 根據前序遍歷的定義可知，每個當前數組的第一個元素就是當前子樹的根節點的值 - 在中序遍歷數組中找到這個值，設其下標為`inRoot` - 當前中序遍歷數組的起點`inStart`到`inRoot`之間就是左子樹，其長度`leftChldLen`為`inRoot-inStart` - 當前中序遍歷數組的終點`inEnd`和`inRoot`之間就是右子樹 - 前序遍歷和中序遍歷中左子樹的長度是相等的，所以在前序遍歷數組中，根節點下標`preStart`往后數`leftChldLen`即為左子樹的最后一個節點，其下標為`preStart+leftChldLen`，右子樹的第一個節點下標為`preStart+leftChldLen+1`。 **PLEASE READ THE CODE BEFORE READING THIS PART** If you can't figure out how to get the index of the left and right child, please read this. - index of current node in preorder array is preStart(or whatever your call it), it's the root of a subtree. - according to the properties of preoder traversal, all right sub-tree nodes are behine all left sub-tree nodes. The length of left sub-tree can help us to divide left and right sub-trees. - the length of left sub-tree can be find in the inorder traversal. The location of current node is `inRoot`(or whatever your call it). The start index of current inorder array is `inStart`(or whatever your call it). So, the lenght of the left sub-tree is `leftChldLen = inRoot - inStart`.  ## 代碼/Code - Java ``` <pre class="calibre18">``` <span class="hljs-title">/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>{ <span class="hljs-function"><span class="hljs-keyword">public</span> TreeNode <span class="hljs-title">buildTree</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] preorder, <span class="hljs-keyword">int</span>[] inorder)</span> </span>{ <span class="hljs-keyword">if</span> (preorder.length != inorder.length) <span class="hljs-keyword">return</span> <span class="hljs-keyword">null</span>; HashMap<Integer, Integer> map = <span class="hljs-keyword">new</span> HashMap<> (); <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i=<span class="hljs-params">0</span>; i<inorder.length; i++) { map.put(inorder[i], i); } <span class="hljs-keyword">return</span> helper(preorder, <span class="hljs-params">0</span>, preorder.length-<span class="hljs-params">1</span>, inorder, <span class="hljs-params">0</span>, inorder.length-<span class="hljs-params">1</span>, map); } <span class="hljs-function"><span class="hljs-keyword">public</span> TreeNode <span class="hljs-title">helper</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] preorder, <span class="hljs-keyword">int</span> preStart, <span class="hljs-keyword">int</span> preEnd, <span class="hljs-keyword">int</span>[] inorder, <span class="hljs-keyword">int</span> inStart, <span class="hljs-keyword">int</span> inEnd, HashMap<Integer, Integer> map)</span> </span>{ <span class="hljs-keyword">if</span> (preStart>preEnd || inStart>inEnd) <span class="hljs-keyword">return</span> <span class="hljs-keyword">null</span>; TreeNode root = <span class="hljs-keyword">new</span> TreeNode(preorder[prestart]); <span class="hljs-keyword">int</span> inRoot = map.get(preorder[preStart]); <span class="hljs-keyword">int</span> leftChldLen = inRoot - inStart; root.left = helper(preorder, preStart+<span class="hljs-params">1</span>, preStart+leftChldLen, inorder, inStart, inRoot-<span class="hljs-params">1</span>, map); root.left = helper(preorder, preStart+leftChldLen+<span class="hljs-params">1</span>, preEnd, inorder, inRoot+<span class="hljs-params">1</span>, inEnd, map); <span class="hljs-keyword">return</span> root; } } ``` ```