日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
LeetCode題解之重建二叉樹

前言

成都創(chuàng)新互聯(lián)主要從事成都網(wǎng)站建設(shè)、網(wǎng)站設(shè)計、網(wǎng)頁設(shè)計、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)靖西,10余年網(wǎng)站建設(shè)經(jīng)驗,價格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):13518219792

今天繼續(xù)二叉樹相關(guān)的算法題

題目

輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。

例如，給出

前序遍歷 preorder = [3,9,20,15,7]

中序遍歷 inorder = [9,3,15,20,7]

返回如下的二叉樹：

 
 
 
 
    
  
  
  
  
  1.  3 
    2.   
  
  
  
  2.  / \ 
    3.   
  
  
  
  3. 9  20 
    4.   
  
  
  
  4.   /  \ 
    5.   
  
  
  
  5.  15   7 
    6.

題解

上周說過 前序遍歷和后序遍歷，其實這種前序、中序、后序都是相對于中間節(jié)點的處理順序。

比如先序遍歷的順序就應(yīng)該是：

[ 根節(jié)點 | 左子樹 | 右子樹 ]

同理，中序遍歷的順序就是：

[ 左子樹 | 根節(jié)點 | 右子樹 ]

所以前序遍歷的第一個元素肯定就是 根節(jié)點。

然后，我們就能在 中序遍歷找到根節(jié)點，并正確把中序遍歷區(qū)分為三部分，也就是左子樹中序、根節(jié)點、右子樹中序。

舉個例子:

如果只有三個元素，那么到這里就能結(jié)束了，因為樹已經(jīng)能畫出來了。

比如前序是【3，9，20】，中序是【9，3，20】

我們根據(jù)中序知道了根節(jié)點3，然后在中序中就能區(qū)分出左子樹節(jié)點9，根節(jié)點3，右子樹節(jié)點20。

現(xiàn)在我們擴散開，如果不止3個節(jié)點呢?

舉例2:

如果是5個元素，比如前序是[3,9,20,15,7]，中序是[9,3,15,20,7]

經(jīng)過第一次分割，我們把中序分成了左子樹9，根節(jié)點3，右子樹【15，20，7】

這時候，右子樹該怎么分呢?跟節(jié)點是什么呢?又不知道了。

所以這時候要再聯(lián)系到前序遍歷，根據(jù)我們所知道的左子樹節(jié)點，得出前序中右子樹應(yīng)該為【20，15，7】，所以右子樹的根節(jié)點為20。

總之，就是前序和中序互相幫助，最終通過遞歸完成我們樹的構(gòu)建。

解法1

解法1就是依靠遞歸。

遞歸的過程就是找出每個父節(jié)點的左子樹節(jié)點和右子樹節(jié)點，一共三個值。

而最終的取值都是從前序列表中取值，其實就是取每個小樹的父節(jié)點。

而中序遍歷數(shù)組的作用就是找到 每次父節(jié)點在中序遍歷數(shù)組中的位置。

得出如下算法。

 
 
 
 
    
  
  
  
  
  1. /** 
    2.   
  
  
  
  2.  * Definition for a binary tree node. 
    3.   
  
  
  
  3.  * public class TreeNode { 
    4.   
  
  
  
  4.  *     int val; 
    5.   
  
  
  
  5.  *     TreeNode left; 
    6.   
  
  
  
  6.  *     TreeNode right; 
    7.   
  
  
  
  7.  *     TreeNode(int x) { val = x; } 
    8.   
  
  
  
  8.  * } 
    9.   
  
  
  
  9.  */ 
    10.   
  
  
  
  10. class Solution { 
    11.   
  
  
  
  11.     int[] preorder; 
    12.   
  
  
  
  12.     HashMap dic = new HashMap<>(); 
    13.   
  
  
  
  13.     public TreeNode buildTree(int[] preorder, int[] inorder) { 
    14.   
  
  
  
  14.         this.preorder = preorder; 
    15.   
  
  
  
  15.         for(int i = 0; i < inorder.length; i++) 
    16.   
  
  
  
  16.             dic.put(inorder[i], i); 
    17.   
  
  
  
  17.         return recur(0, 0, inorder.length - 1); 
    18.   
  
  
  
  18.     } 
    19.   
  
  
  
  19.     TreeNode recur(int root, int left, int right) { 
    20.   
  
  
  
  20.         if(left > right) return null;         
    21.   
  
  
  
  21.         //根節(jié)點                   
    22.   
  
  
  
  22.         TreeNode node = new TreeNode(preorder[root]);    
    23.   
  
  
  
  23.         //分割點     
    24.   
  
  
  
  24.         int i = dic.get(preorder[root]);         
    25.   
  
  
  
  25.         node.left = recur(root + 1, left, i - 1);  
    26.   
  
  
  
  26.         node.right = recur(root + i - left + 1, i + 1, right);  
    27.   
  
  
  
  27.         return node;       
    28.   
  
  
  
  28.     } 
    29.   
  
  
  
  29. } 
    30.

其中每次取右子樹的根節(jié)點需要注意：

左子樹的節(jié)點數(shù)為i-left。

所以在前序遍歷數(shù)組中，左子樹的節(jié)點+根節(jié)點位置，就是左子樹的最后一個節(jié)點位置，也就是root+i-left。

最后得出右子樹的根節(jié)點為：root + i - left + 1

而遞歸的結(jié)束條件就是，左右子樹節(jié)點相遇，也就是left>right。

時間復(fù)雜度

O(n)，n為樹的節(jié)點數(shù)量。

空間復(fù)雜度

O(N)，用到了HashMap。

解法2

還有一種辦法叫做迭代方法，這個方法挺巧妙的，當(dāng)時也是看了很久的官方解答才想明白的，哈哈。

它的主要思想是理解前序遍歷和中序遍歷的規(guī)則，然后一個個從前序遍歷中取值，并放到合適的位置。

比如以下這個二叉樹：

 
 
 
 
    
  
  
  
  
  1.         3 
    2.   
  
  
  
  2.        / \ 
    3.   
  
  
  
  3.       9  20 
    4.   
  
  
  
  4.      /  /  \ 
    5.   
  
  
  
  5.     8  15   7 
    6.   
  
  
  
  6.    / \ 
    7.   
  
  
  
  7.   5  10 
    8.   
  
  
  
  8.  / 
    9.   
  
  
  
  9. 4 
    10.

前序遍歷，可以發(fā)現(xiàn)是首先把最左邊的節(jié)點列出來，也就是 3，9，8，5，4

而中序列表是反著來的，從最左邊的下面開始，往上列，如果發(fā)現(xiàn)某個節(jié)點有右子節(jié)點，就開始往右邊列。

比如 4，5，8。這時候發(fā)現(xiàn)8有右子節(jié)點，那么就開始數(shù) 10 ，然后繼續(xù)最左邊往上，9，3。

最后列一下完整的前序和中序：

preorder = [3, 9, 8, 5, 4, 10, 20, 15, 7] inorder = [4, 5, 8, 10, 9, 3, 15, 20, 7]

總之，前序是從左邊列開始，從上往下排。中序就是從左邊列開始，從下往上排。

看看代碼：

 
 
 
 
    
  
  
  
  
  1. class Solution { 
    2.   
  
  
  
  2.     public TreeNode buildTree(int[] preorder, int[] inorder) { 
    3.   
  
  
  
  3.         if (preorder == null || preorder.length == 0) { 
    4.   
  
  
  
  4.             return null; 
    5.   
  
  
  
  5.         } 
    6.   
  
  
  
  6.         TreeNode root = new TreeNode(preorder[0]); 
    7.   
  
  
  
  7.         Deque stack = new LinkedList(); 
    8.   
  
  
  
  8.         stack.push(root); 
    9.   
  
  
  
  9.         int inorderIndex = 0; 
    10.   
  
  
  
  10.         for (int i = 1; i < preorder.length; i++) { 
    11.   
  
  
  
  11.             int preorderVal = preorder[i]; 
    12.   
  
  
  
  12.             TreeNode node = stack.peek(); 
    13.   
  
  
  
  13.             if (node.val != inorder[inorderIndex]) { 
    14.   
  
  
  
  14.                 node.left = new TreeNode(preorderVal); 
    15.   
  
  
  
  15.                 stack.push(node.left); 
    16.   
  
  
  
  16.             } else { 
    17.   
  
  
  
  17.                 while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) { 
    18.   
  
  
  
  18.                     node = stack.pop(); 
    19.   
  
  
  
  19.                     inorderIndex++; 
    20.   
  
  
  
  20.                 } 
    21.   
  
  
  
  21.                 node.right = new TreeNode(preorderVal); 
    22.   
  
  
  
  22.                 stack.push(node.right); 
    23.   
  
  
  
  23.             } 
    24.   
  
  
  
  24.         } 
    25.   
  
  
  
  25.         return root; 
    26.   
  
  
  
  26.     } 
    27.   
  
  
  
  27. } 
    28.

if語句是為了找到左列最后一個節(jié)點，比如上述例子中的4。

while循環(huán)是當(dāng)發(fā)現(xiàn)有右節(jié)點的時候，要找到右節(jié)點的父節(jié)點，然后添加進去。

大家可以手動試試，解法2確實不太好理解。

至少解法1的遞歸方法是要掌握的。

時間復(fù)雜度

O(n)

空間復(fù)雜度

O(n)

參考

https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/solution/

本文轉(zhuǎn)載自微信公眾號「碼上積木」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系碼上積木公眾號。


名稱欄目：LeetCode題解之重建二叉樹
URL地址：http://www.5511xx.com/article/dhddhhj.html