我們從二叉樹(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：

輸入："1-2--3--4-5--6--7"
輸出：[1,2,5,3,4,6,7]

示例 2：

輸入："1-2--3---4-5--6---7"
輸出：[1,2,5,3,null,6,null,4,null,7]

示例 3：

輸入："1-401--349---90--88"
輸出：[1,401,null,349,88,90]

提示：

原始樹(shù)中的節(jié)點(diǎn)數(shù)介于 1 和 1000 之間。
每個(gè)節(jié)點(diǎn)的值介于 1 和 10 ^ 9 之間。

思路：

利用棧

兩個(gè)相鄰的結(jié)點(diǎn)只可能存在兩種關(guān)系

1.后者是前者的左子節(jié)點(diǎn)

2.后者與前者無(wú)關(guān)，是更前面某一個(gè)節(jié)點(diǎn)的右子節(jié)點(diǎn)

/**

?*?Definition?for?a?binary?tree?node.

?*?public?class?TreeNode?{

?*?????int?val;

?*?????TreeNode?left;

?*?????TreeNode?right;

?*?????TreeNode(int?x)?{?val?=?x;?}

?*?}

?*/

class?Solution?{

????public?TreeNode?recoverFromPreorder(String?S)?{

????????if(S==null||S.length()==0){

????????????return?null;

????????}

????????Stack<TreeNode>?stack?=?new?Stack<>();

????????TreeNode?root?=?new?TreeNode(S.charAt(0)-'0');

????????int?index=0;

????????while(index<S.length()){

????????????int?level?=?0;

? ? ? ? ? //記錄當(dāng)前找個(gè)節(jié)點(diǎn)處于第幾層（通過(guò)看他前面有幾條短線）

????????????while(S.charAt(index)=='-'){

????????????????index++;

????????????????level++;

????????????}

????????????int?value?=?0;

????????????while?(index?<?S.length()?&&?Character.isDigit(S.charAt(index)))?{

????????????????value?=?value?*?10?+?(S.charAt(index)?-?'0');

????????????????++index;

????????????}

????????????TreeNode?temp?=?new?TreeNode(value);

? ? ? ? ? ? //如果棧中節(jié)點(diǎn)遍歷到的層數(shù)和新節(jié)點(diǎn)處于的層數(shù)一樣，那么新節(jié)點(diǎn)是之前節(jié)點(diǎn)的左子節(jié)點(diǎn)，壓入棧中

????????????if(level==stack.size()){

????????????????if(!stack.isEmpty()){

????????????????????stack.peek().left?=?temp;

????????????????}

? ? ? ? ? ?//依次遍歷到新節(jié)點(diǎn)父親的層數(shù)，其他的出棧

????????????}else{

????????????????while(level!=stack.size()){

????????????????????stack.pop();

????????????????}

????????????????stack.peek().right=temp;

????????????}

????????????stack.push(temp);

????????}

? ? ?//有的結(jié)點(diǎn)可能未出棧，依次退棧，只留下樹(shù)根返回

????????while(stack.size()>1){

????????????stack.pop();

????????}

????????return?stack.peek();

????}

}

總結(jié)

以上是生活随笔為你收集整理的Leetcode--1028. 从先序遍历还原二叉树（Java）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。