樹(shù) 從先序遍歷還原二叉樹(shù)

題目

難度：困難

我們從二叉樹(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 之間。

題解

class Solution {
    public TreeNode recoverFromPreorder(String S) {
        Deque<TreeNode> path = new LinkedList<TreeNode>();
        int pos = 0;
        while (pos < S.length()) {
            int level = 0;
            while (S.charAt(pos) == '-') {
                ++level;
                ++pos;
            }
            int value = 0;
            while (pos < S.length() && Character.isDigit(S.charAt(pos))) {
                value = value * 10 + (S.charAt(pos) - '0');
                ++pos;
            }
            TreeNode node = new TreeNode(value);
            if (level == path.size()) {
                if (!path.isEmpty()) {
                    path.peek().left = node;
                }
            }
            else {
                while (level != path.size()) {
                    path.pop();
                }
                path.peek().right = node;
            }
            path.push(node);
        }
        while (path.size() > 1) {
            path.pop();
        }
        return path.peek();
    }
}

復(fù)雜度分析

時(shí)間復(fù)雜度：O(∣s∣)，其中 ∣s∣ 是字符串 s的長(zhǎng)度。我們的算法不斷地從 SSS 中取出一個(gè)節(jié)點(diǎn)的信息，直到取完為止。在這個(gè)過(guò)程中，我們實(shí)際上是對(duì) SSS 進(jìn)行了一次遍歷。

時(shí)間復(fù)雜度：O(h)，其中 h是還原出的二叉樹(shù)的高度。除了作為答案返回的二叉樹(shù)使用的空間以外，我們使用了一個(gè)棧幫助我們進(jìn)行迭代。由于棧中存放了從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)這一路徑上的所有節(jié)點(diǎn)，因此最多只會(huì)同時(shí)由 h 個(gè)節(jié)點(diǎn)。

方法解析

1.deque函數(shù)：

deque容器為一個(gè)給定類(lèi)型的元素進(jìn)行線性處理，像向量一樣，它能夠快速地隨機(jī)訪問(wèn)任一個(gè)元素，并且能夠高效地插入和刪除容器的尾部元素。但它又與vector不同，deque支持高效插入和刪除容器的頭部元素，因此也叫做雙端隊(duì)列。deque類(lèi)常用的函數(shù)如下。

2.Character.isDigit(char ch)

返回值 如果字符為數(shù)字，則返回 true；否則返回 false。

實(shí)例

public class Test {
    public static void main(String args[]) {
        System.out.println(Character.isDigit('c'));
        System.out.println(Character.isDigit('5'));
    }
}

以上程序執(zhí)行結(jié)果為：

false true