<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 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`. ![](https://img.kancloud.cn/7a/44/7a447de04fd12d69d13114cef4667837_864x635.jpg) ## 代碼/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; } } ``` ```
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看