本篇內(nèi)容主要講解“LeetCode題解之如何重建二叉樹”，感興趣的朋友不妨來看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“LeetCode題解之如何重建二叉樹”吧!

創(chuàng)新互聯(lián)建站服務(wù)項(xiàng)目包括洛陽網(wǎng)站建設(shè)、洛陽網(wǎng)站制作、洛陽網(wǎng)頁制作以及洛陽網(wǎng)絡(luò)營(yíng)銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢(shì)、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，洛陽網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到洛陽省份的部分城市，未來相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

題目

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

例如，給出

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

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

返回如下的二叉樹：

 3  / \ 9  20   /  \  15   7

題解

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

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

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

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

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

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

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

舉個(gè)例子:

如果只有三個(gè)元素，那么到這里就能結(jié)束了，因?yàn)闃湟呀?jīng)能畫出來了。

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

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

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

舉例2:

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

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

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

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

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

解法1

解法1就是依靠遞歸。

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

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

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

得出如下算法。

/**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode(int x) { val = x; }  * }  */ class Solution {     int[] preorder;     HashMap<Integer, Integer> dic = new HashMap<>();     public TreeNode buildTree(int[] preorder, int[] inorder) {         this.preorder = preorder;         for(int i = 0; i < inorder.length; i++)             dic.put(inorder[i], i);         return recur(0, 0, inorder.length - 1);     }     TreeNode recur(int root, int left, int right) {         if(left > right) return null;                 //根節(jié)點(diǎn)                           TreeNode node = new TreeNode(preorder[root]);            //分割點(diǎn)             int i = dic.get(preorder[root]);                 node.left = recur(root + 1, left, i - 1);          node.right = recur(root + i - left + 1, i + 1, right);          return node;           } }

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

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

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

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

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

時(shí)間復(fù)雜度

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

空間復(fù)雜度

O(N)，用到了HashMap。

解法2

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

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

比如以下這個(gè)二叉樹：

        3        / \       9  20      /  /  \     8  15   7    / \   5  10  / 4

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

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

比如 4，5，8。這時(shí)候發(fā)現(xiàn)8有右子節(jié)點(diǎn)，那么就開始數(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]

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

看看代碼：

class Solution {     public TreeNode buildTree(int[] preorder, int[] inorder) {         if (preorder == null || preorder.length == 0) {             return null;         }         TreeNode root = new TreeNode(preorder[0]);         Deque<TreeNode> stack = new LinkedList<TreeNode>();         stack.push(root);         int inorderIndex = 0;         for (int i = 1; i < preorder.length; i++) {             int preorderVal = preorder[i];             TreeNode node = stack.peek();             if (node.val != inorder[inorderIndex]) {                 node.left = new TreeNode(preorderVal);                 stack.push(node.left);             } else {                 while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {                     node = stack.pop();                     inorderIndex++;                 }                 node.right = new TreeNode(preorderVal);                 stack.push(node.right);             }         }         return root;     } }

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

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

到此，相信大家對(duì)“LeetCode題解之如何重建二叉樹”有了更深的了解，不妨來實(shí)際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！

分享標(biāo)題：LeetCode題解之如何重建二叉樹
轉(zhuǎn)載來于：http://jinyejixie.com/article42/jjiphc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供、網(wǎng)站設(shè)計(jì)、全網(wǎng)營(yíng)銷推廣、定制開發(fā)、網(wǎng)站收錄、建站公司

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)