資訊專欄INFORMATION COLUMN
摘要：解題思路利用遞歸思想，先序遍歷的第一個元素就是根節(jié)點，然后在中序遍歷中尋找該節(jié)點，該節(jié)點左邊的就是左子樹，右邊的是右子樹。
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.解題思路
利用遞歸思想，先序遍歷的第一個元素就是根節(jié)點，然后在中序遍歷中尋找該節(jié)點，該節(jié)點左邊的就是左子樹，右邊的是右子樹。
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.
解題思路
后序遍歷，所以邏輯和上一題一樣，但是我們要從后序遍歷的最后一個節(jié)點開始，這樣我們就得先處理右子樹，再處理左子樹。
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)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/69807.html
摘要：做了幾道二分法的題目練手，發(fā)現(xiàn)這道題已經(jīng)淡忘了，記錄一下。這道題目的要點在于找的區(qū)間。邊界條件需要注意若或數(shù)組為空，返回空當(dāng)前進(jìn)到超出末位，或超過，返回空每次創(chuàng)建完根節(jié)點之后，要將加，才能進(jìn)行遞歸。 Construct Binary Tree from Inorder and Preorder Traversal Problem Given preorder and inorder t...
摘要：思路在的順序里，先，然后再左右。所以根據(jù)可以知道的。接著再分別在和的里面重復(fù)找以及左右的過程。首先的包括和，以及對應(yīng)的起始和結(jié)束位置，對應(yīng)的起始和結(jié)束位置。返回值為，因為每個里要一個，同時找到它的和，左右節(jié)點通過返回值獲得。同時的不需要了。 From Preorder and Inorder 思路在preorder的順序里，先root，然后再左右。所以根據(jù)preorder可以知道roo...
摘要：二分法復(fù)雜度時間空間思路我們先考察先序遍歷序列和中序遍歷序列的特點。對于中序遍歷序列，根在中間部分，從根的地方分割，前半部分是根的左子樹，后半部分是根的右子樹。 Construct Binary Tree from Preorder and Inorder Traversal Given preorder and inorder traversal of a tree, constru...
摘要：題目要求將二叉搜索樹序列化和反序列化，序列化是指將樹用字符串的形式表示，反序列化是指將字符串形式的樹還原成原來的樣子。假如二叉搜索樹的節(jié)點較多，該算法將會占用大量的額外空間。 題目要求 Serialization is the process of converting a data structure or object into a sequence of bits so that...
摘要：代碼解題思路先序遍歷，同樣用迭代實現(xiàn)，借助棧。先將根節(jié)點入棧先序遍歷，所以直接出根節(jié)點因為順序是根，左節(jié)點，右節(jié)點，所以我們在壓棧的時候要先壓右節(jié)點，再壓左節(jié)點。所以我們自定義了一個類，添加了的屬性，來表明該節(jié)點是否已經(jīng)被訪問過了。 Binary Tree Inorder TraversalGiven a binary tree, return the inorder traversa...
閱讀 1531·2021-11-25 09:43
閱讀 4079·2021-11-15 11:37
閱讀 3208·2021-08-17 10:13
閱讀 3515·2019-08-30 14:16
閱讀 3546·2019-08-26 18:37
閱讀 2502·2019-08-26 11:56
閱讀 1145·2019-08-26 10:42
閱讀 623·2019-08-26 10:39
