2023-06-14：我們從二叉樹(shù)的根節(jié)點(diǎn) root 開(kāi)始進(jìn)行深度優(yōu)先搜索。 在遍歷中的每個(gè)節(jié)點(diǎn)
2023-06-14：我們從二叉樹(shù)的根節(jié)點(diǎn) root 開(kāi)始進(jìn)行深度優(yōu)先搜索。
在遍歷中的每個(gè)節(jié)點(diǎn)處，我們輸出 D 條短劃線（其中 D 是該節(jié)點(diǎn)的深度）
然后輸出該節(jié)點(diǎn)的值。（如果節(jié)點(diǎn)的深度為 D，則其直接子節(jié)點(diǎn)的深度為 D + 1
根節(jié)點(diǎn)的深度為 0
如果節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)，那么保證該子節(jié)點(diǎn)為左子節(jié)點(diǎn)
給出遍歷輸出 S，還原樹(shù)并返回其根節(jié)點(diǎn) root。
輸入："1-2--3--4-5--6--7"。
輸出：[1,2,5,3,4,6,7]。
答案2023-06-14：
大體過(guò)程如下：
1.根據(jù)輸入的遍歷字符串 S 來(lái)構(gòu)建一個(gè)二叉樹(shù)。
2.定義一個(gè)結(jié)構(gòu)體類(lèi)型 TreeNode，表示二叉樹(shù)的節(jié)點(diǎn)，包括節(jié)點(diǎn)值 Val，左子節(jié)點(diǎn) Left，右子節(jié)點(diǎn) Right。
3.定義一個(gè)數(shù)組 queue，用于存儲(chǔ)節(jié)點(diǎn)的深度和值。
4.定義兩個(gè)全局變量 l 和 r，表示隊(duì)列的左右指針。
5.定義一個(gè)函數(shù) recoverFromPreorder，用于根據(jù)遍歷字符串 S 還原二叉樹(shù)。
6.遍歷字符串 S 的每一個(gè)字符：
a.如果該字符不為 '-'（即為數(shù)字字符），記錄下該數(shù)字，直到該數(shù)字記錄完畢。
b.如果該字符為 '-'，則表示該數(shù)字已經(jīng)記錄完畢，將該數(shù)字加入到 queue 數(shù)組中，并將 pickLevel 置為 true。
c.如果該字符是 '-' 或者到達(dá)字符串末尾，表示該數(shù)字已經(jīng)記錄完畢，將 lvel 記錄到隊(duì)列中， pickLevel 置為 false 。
d.如果該字符是 '-'，表示深度加 1；否則，將該數(shù)字加入到 number 中。
7.處理掉最后一個(gè)數(shù)字，將其加入到隊(duì)列 queue 中。
8.定義一個(gè)遞歸函數(shù) f，用于生成節(jié)點(diǎn)，并構(gòu)建二叉樹(shù)。
9.取出隊(duì)列的第一個(gè)元素 level，它是當(dāng)前節(jié)點(diǎn)的深度。
10.取出隊(duì)列的第二個(gè)元素 val，它是當(dāng)前節(jié)點(diǎn)的值。
11.生成一個(gè) TreeNode 類(lèi)型的結(jié)構(gòu)體，元素值為 val，左子節(jié)點(diǎn)和右子節(jié)點(diǎn)置為 nil。
12.如果隊(duì)列不為空，且隊(duì)列的下一個(gè)元素的值大于當(dāng)前節(jié)點(diǎn)深度 level，則遞歸進(jìn)入左子節(jié)點(diǎn)，生成左子樹(shù)。
13.同樣，如果隊(duì)列不為空，且隊(duì)列的下一個(gè)元素的值大于當(dāng)前節(jié)點(diǎn)深度 level，則遞歸進(jìn)入右子節(jié)點(diǎn)，生成右子樹(shù)。
14.返回根節(jié)點(diǎn) head。
時(shí)間復(fù)雜度為 O(n)，其中 n 是遍歷字符串 S 的長(zhǎng)度。需要遍歷字符串 S 一次，并將每個(gè)節(jié)點(diǎn)入隊(duì)一次，然后根據(jù)隊(duì)列中的節(jié)點(diǎn)數(shù)構(gòu)建二叉樹(shù)，構(gòu)建二叉樹(shù)的時(shí)間復(fù)雜度也是 O(n)。因此，總時(shí)間復(fù)雜度為 O(n)。
空間復(fù)雜度為 O(n)，需要一個(gè)數(shù)組來(lái)存儲(chǔ)節(jié)點(diǎn)的深度和值，并將其入隊(duì)。由于二叉樹(shù)不一定是滿二叉樹(shù)，因此最多需要存儲(chǔ) 2n 個(gè)節(jié)點(diǎn)的深度和值信息。因此，總空間復(fù)雜度為 O(n)。
go完整代碼如下：
package?main
import?(
????"fmt"
????"strconv"
)
type?TreeNode?struct?{
????Val???int
????Left??*TreeNode
????Right?*TreeNode
}
const?MAXN?=?2001
var?queue?[MAXN]int
var?l,?r?int
func?recoverFromPreorder(traversal?string)?*TreeNode?{
????l?=?0
????r?=?0
????number?:=?0
????level?:=?0
????pickLevel?:=?true
????for?i?:=?0;?i?<?len(traversal);?i++?{
????????c?:=?traversal[i]
????????if?c?!=?'-'?{
????????????if?pickLevel?{
????????????????queue[r]?=?level
????????????????level?=?0
????????????????r++
????????????????pickLevel?=?false
????????????}
????????????d,?_?:=?strconv.Atoi(string(c))
????????????number?=?number*10?+?d
????????}?else?{
????????????if?!pickLevel?{
????????????????queue[r]?=?number
????????????????number?=?0
????????????????r++
????????????????pickLevel?=?true
????????????}
????????????level++
????????}
????}
????queue[r]?=?number
????return?f()
}
func?f()?*TreeNode?{
????level?:=?queue[l]
????head?:=?&TreeNode{Val:?queue[l+1],?Left:?nil,?Right:?nil}
????l?+=?2
????if?l?<?r?&&?queue[l]?>?level?{
????????head.Left?=?f()
????}
????if?l?<?r?&&?queue[l]?>?level?{
????????head.Right?=?f()
????}
????return?head
}
func?main()?{
????traversal?:=?"1-2--3--4-5--6--7"
????result?:=?recoverFromPreorder(traversal)
????fmt.Printf("%+v\n",?result)
}
rust完整代碼如下：
use?std::cell::RefCell;
use?std::rc::Rc;
pub?struct?TreeNode?{
????pub?val:?i32,
????pub?left:?Option<Rc<RefCell<TreeNode>>>,
????pub?right:?Option<Rc<RefCell<TreeNode>>>,
}
impl?TreeNode?{
????
????pub?fn?new(val:?i32)?->?Self?{
????????TreeNode?{
????????????val,
????????????left:?None,
????????????right:?None,
????????}
????}
}
fn?recover_from_preorder(traversal:?String)?->?Option<Rc<RefCell<TreeNode>>>?{
????let?mut?queue?=?vec![0;?2001];
????let?mut?l?=?0;
????let?mut?r?=?0;
????let?mut?number?=?0;
????let?mut?level?=?0;
????let?mut?pick_level?=?true;
????for?c?in?traversal.chars()?{
????????if?c?!=?'-'?{
????????????if?pick_level?{
????????????????queue[r]?=?level;
????????????????level?=?0;
????????????????r?+=?1;
????????????????pick_level?=?false;
????????????}
????????????number?=?number?*?10?+?c.to_digit(10).unwrap()?as?i32;
????????}?else?{
????????????if?!pick_level?{
????????????????queue[r]?=?number;
????????????????number?=?0;
????????????????r?+=?1;
????????????????pick_level?=?true;
????????????}
????????????level?+=?1;
????????}
????}
????queue[r]?=?number;
????let?queue_len?=?r?+?1;
????f(&mut?queue,?&mut?l,?queue_len,?0)
}
fn?f(queue:?&mut?[i32],?l:?&mut?usize,?r:?usize,?level:?i32)?->?Option<Rc<RefCell<TreeNode>>>?{
????if?*l?>=?r?||?queue[*l]?!=?level?{
????????None
????}?else?{
????????*l?+=?1;
????????let?head?=?Rc::new(RefCell::new(TreeNode::new(queue[*l])));
????????*l?+=?1;
????????head.borrow_mut().left?=?f(queue,?l,?r,?level?+?1);
????????head.borrow_mut().right?=?f(queue,?l,?r,?level?+?1);
????????Some(head)
????}
}
fn?main()?{
????let?traversal?=?String::from("1-2--3--4-5--6--7");
????let?result?=?recover_from_preorder(traversal);
????println!("{:#?}",?result);
}
c++完整代碼如下：
using?namespace?std;
struct?TreeNode?{
????int?val;
????TreeNode*?left;
????TreeNode*?right;
????TreeNode()?:?val(0),?left(nullptr),?right(nullptr)?{}
????TreeNode(int?x)?:?val(x),?left(nullptr),?right(nullptr)?{}
????TreeNode(int?x,?TreeNode*?left,?TreeNode*?right)?:?val(x),?left(left),?right(right)?{}
};
TreeNode*?f();
const?int?MAXN?=?2001;
int?queue[MAXN];
int?l,?r;
TreeNode*?recoverFromPreorder(string?traversal)?{
????l?=?0;
????r?=?0;
????int?number?=?0;
????int?level?=?0;
????bool?pickLevel?=?true;
????for?(int?i?=?0;?i?<?traversal.size();?i++)?{
????????char?c?=?traversal[i];
????????if?(c?!=?'-')?{
????????????if?(pickLevel)?{
????????????????queue[r++]?=?level;
????????????????level?=?0;
????????????????pickLevel?=?false;
????????????}
????????????number?=?number?*?10?+?c?-?'0';
????????}
????????else?{
????????????if?(!pickLevel)?{
????????????????queue[r++]?=?number;
????????????????number?=?0;
????????????????pickLevel?=?true;
????????????}
????????????level++;
????????}
????}
????queue[r++]?=?number;
????return?f();
}
TreeNode*?f()?{
????int?level?=?queue[l++];
????TreeNode*?head?=?new?TreeNode(queue[l++]);
????if?(l?<?r?&&?queue[l]?>?level)?{
????????head->left?=?f();
????}
????if?(l?<?r?&&?queue[l]?>?level)?{
????????head->right?=?f();
????}
????return?head;
}
int?main()?{
????string?traversal?=?"1-2--3--4-5--6--7";
????TreeNode*?result?=?recoverFromPreorder(traversal);
????cout?<<?result->val?<<?endl;
????cout?<<?result->left->val?<<?endl;
????cout?<<?result->right->val?<<?endl;
????cout?<<?result->left->left->val?<<?endl;
????cout?<<?result->left->right->val?<<?endl;
????cout?<<?result->right->left->val?<<?endl;
????cout?<<?result->right->right->val?<<?endl;
????return?0;
}
c語(yǔ)言完整代碼如下：
struct?TreeNode?{
????int?val;
????struct?TreeNode*?left;
????struct?TreeNode*?right;
};
struct?TreeNode*?f();
int?queue[MAXN];
int?l,?r;
struct?TreeNode*?recoverFromPreorder(char*?traversal)?{
????l?=?0;
????r?=?0;
????int?number?=?0;
????int?level?=?0;
????int?pickLevel?=?1;
????int?len?=?strlen(traversal);
????for?(int?i?=?0;?i?<?len;?i++)?{
????????char?c?=?traversal[i];
????????if?(c?!=?'-')?{
????????????if?(pickLevel)?{
????????????????queue[r++]?=?level;
????????????????level?=?0;
????????????????pickLevel?=?0;
????????????}
????????????number?=?number?*?10?+?c?-?'0';
????????}
????????else?{
????????????if?(!pickLevel)?{
????????????????queue[r++]?=?number;
????????????????number?=?0;
????????????????pickLevel?=?1;
????????????}
????????????level++;
????????}
????}
????queue[r++]?=?number;
????return?f();
}
struct?TreeNode*?f()?{
????int?level?=?queue[l++];
????struct?TreeNode*?head?=?(struct?TreeNode*)malloc(sizeof(struct?TreeNode));
????head->val?=?queue[l++];
????head->left?=?NULL;
????head->right?=?NULL;
????if?(l?<?r?&&?queue[l]?>?level)?{
????????head->left?=?f();
????}
????if?(l?<?r?&&?queue[l]?>?level)?{
????????head->right?=?f();
????}
????return?head;
}
int?main()?{
????char?traversal[]?=?"1-2--3--4-5--6--7";
????struct?TreeNode*?result?=?recoverFromPreorder(traversal);
????printf("%d\n",?result->val);
????printf("%d\n",?result->left->val);
????printf("%d\n",?result->right->val);
????printf("%d\n",?result->left->left->val);
????printf("%d\n",?result->left->right->val);
????printf("%d\n",?result->right->left->val);
????printf("%d\n",?result->right->right->val);
????return?0;
}
