摘要:解題思路利用遞歸思想,先序遍歷的第一個(gè)元素就是根節(jié)點(diǎn),然后在中序遍歷中尋找該節(jié)點(diǎn),該節(jié)點(diǎn)左邊的就是左子樹,右邊的是右子樹。
Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
1.解題思路
利用遞歸思想,先序遍歷的第一個(gè)元素就是根節(jié)點(diǎn),然后在中序遍歷中尋找該節(jié)點(diǎn),該節(jié)點(diǎn)左邊的就是左子樹,右邊的是右子樹。
2.代碼
public class Solution { int curroot=0; public TreeNode buildTree(int[] preorder, int[] inorder) { return build(0,inorder.length-1,preorder,inorder); } private TreeNode build(int instart,int inend,int[] preorder, int[] inorder){ if(curroot==preorder.length||instart>inend) return null; TreeNode root=new TreeNode(preorder[curroot]); //find mid in inorder; int mid=0; for(int i=instart;i<=inend;i++){ if(inorder[i]==preorder[curroot]){ mid=i; break; } } curroot++; root.left=build(instart,mid-1,preorder,inorder); root.right=build(mid+1,inend,preorder,inorder); return root; } }
Construct Binary Tree from Inorder and Postorder Traversal
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
解題思路
后序遍歷,所以邏輯和上一題一樣,但是我們要從后序遍歷的最后一個(gè)節(jié)點(diǎn)開始,這樣我們就得先處理右子樹,再處理左子樹。
2.代碼
public class Solution { int curroot=0; public TreeNode buildTree(int[] inorder, int[] postorder) { curroot=postorder.length-1; return build(0,inorder.length-1,inorder,postorder); } private TreeNode build(int instart,int inend,int[] inorder, int[] postorder){ if(curroot<0||instart>inend) return null; TreeNode root=new TreeNode(postorder[curroot]); int mid=0; for(int i=instart;i<=inend;i++){ if(inorder[i]==postorder[curroot]){ mid=i; break; } } curroot--; root.right=build(mid+1,inend,inorder,postorder); root.left=build(instart,mid-1,inorder,postorder); return root; } }
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://m.specialneedsforspecialkids.com/yun/69807.html
摘要:做了幾道二分法的題目練手,發(fā)現(xiàn)這道題已經(jīng)淡忘了,記錄一下。這道題目的要點(diǎn)在于找的區(qū)間。邊界條件需要注意若或數(shù)組為空,返回空當(dāng)前進(jìn)到超出末位,或超過,返回空每次創(chuàng)建完根節(jié)點(diǎn)之后,要將加,才能進(jìn)行遞歸。 Construct Binary Tree from Inorder and Preorder Traversal Problem Given preorder and inorder t...
摘要:思路在的順序里,先,然后再左右。所以根據(jù)可以知道的。接著再分別在和的里面重復(fù)找以及左右的過程。首先的包括和,以及對(duì)應(yīng)的起始和結(jié)束位置,對(duì)應(yīng)的起始和結(jié)束位置。返回值為,因?yàn)槊總€(gè)里要一個(gè),同時(shí)找到它的和,左右節(jié)點(diǎn)通過返回值獲得。同時(shí)的不需要了。 From Preorder and Inorder 思路在preorder的順序里,先root,然后再左右。所以根據(jù)preorder可以知道roo...
摘要:二分法復(fù)雜度時(shí)間空間思路我們先考察先序遍歷序列和中序遍歷序列的特點(diǎn)。對(duì)于中序遍歷序列,根在中間部分,從根的地方分割,前半部分是根的左子樹,后半部分是根的右子樹。 Construct Binary Tree from Preorder and Inorder Traversal Given preorder and inorder traversal of a tree, constru...
摘要:題目要求將二叉搜索樹序列化和反序列化,序列化是指將樹用字符串的形式表示,反序列化是指將字符串形式的樹還原成原來的樣子。假如二叉搜索樹的節(jié)點(diǎn)較多,該算法將會(huì)占用大量的額外空間。 題目要求 Serialization is the process of converting a data structure or object into a sequence of bits so that...
摘要:代碼解題思路先序遍歷,同樣用迭代實(shí)現(xiàn),借助棧。先將根節(jié)點(diǎn)入棧先序遍歷,所以直接出根節(jié)點(diǎn)因?yàn)轫樞蚴歉蠊?jié)點(diǎn),右節(jié)點(diǎn),所以我們?cè)趬簵5臅r(shí)候要先壓右節(jié)點(diǎn),再壓左節(jié)點(diǎn)。所以我們自定義了一個(gè)類,添加了的屬性,來表明該節(jié)點(diǎn)是否已經(jīng)被訪問過了。 Binary Tree Inorder TraversalGiven a binary tree, return the inorder traversa...
閱讀 1527·2021-11-25 09:43
閱讀 4070·2021-11-15 11:37
閱讀 3201·2021-08-17 10:13
閱讀 3509·2019-08-30 14:16
閱讀 3540·2019-08-26 18:37
閱讀 2499·2019-08-26 11:56
閱讀 1139·2019-08-26 10:42
閱讀 617·2019-08-26 10:39