国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

LeetCode 536. Construct Binary Tree from String 從帶

tabalt / 2697人閱讀

摘要：題意從一個帶括號的字符串，構(gòu)建一顆二叉樹。其中當而時，展示為一個空的括號。同時要考慮負數(shù)的情況，所以在取數(shù)字的時候，必須注意所在位置。遇到則從棧中出元素。最后中的元素就是，返回棧頂元素即可。

LeetCode 536. Construct Binary Tree from String

You need to construct a binary tree from a string consisting of parenthesis and integers.

The whole input represents a binary tree. It contains an integer followed by zero, one or two pairs of parenthesis. The integer represents the root"s value and a pair of parenthesis contains a child binary tree with the same structure.

You always start to construct the left child node of the parent first if it exists.

Example:
Input: "4(2(3)(1))(6(5))"
Output: return the tree root node representing the following tree:

       4
     /   
    2     6
   /    / 
  3   1 5

Note:
There will only be "(", ")", "-" and "0" ~ "9" in the input string.
An empty tree is represented by "" instead of ()".

題意：從一個帶括號的字符串，構(gòu)建一顆二叉樹。

解題思路： 本題仔細看字符串可以發(fā)現(xiàn)，每個root,left,right都是以root.val(left.val)(right.val)展示的。其中當left = null而right != null時，left展示為一個空的括號"()"。同時要考慮負數(shù)的情況，所以在取數(shù)字的時候，必須注意index所在位置。我們用一個stack存儲當前構(gòu)建好的TreeNode,每次遇到數(shù)字時，將數(shù)字構(gòu)建成TreeNode,查看是否為stack為空，不為空，則查看stack中頂層元素的左子樹是否已經(jīng)有了，如果沒有，那當前新構(gòu)建的TreeNode就是它的左邊的孩子，否則就是頂層元素的右孩子。遇到")"則從棧中pop出元素。最后stack中的元素就是root，返回root棧頂元素即可。

代碼如下：

    public TreeNode str2tree(String s) {
        if (s == null || s.length() == 0) {
            return null;
        }
        Stack stack = new Stack<>();
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == ")") {
                stack.pop();
            } else {
                if (c >= "0" && c <= "9" || c == "-") {
                    int start = i;
                    while(i + 1 < s.length() && s.charAt(i + 1) >= "0" && s.charAt(i + 1) <= "9") {
                        i++;
                    }
                    TreeNode node = new TreeNode(Integer.valueOf(s.substring(start, i + 1)));
                    if (!stack.isEmpty()) {
                        TreeNode parent = stack.peek();
                        if (parent.left != null) {
                            parent.right = node;
                        } else {
                            parent.left = node;
                        }
                    }
                    stack.push(node);
                }
            }
        }
        if(stack.isEmpty()) {
            return null;
        }
        return stack.peek();

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/71883.html

相關(guān)文章

  • LeetCode 606. Construct String from Binary Tree 二叉

    摘要：題意從一顆二叉樹轉(zhuǎn)為帶括號的字符串。這題是的姊妹題型，該題目的解法在這里解法。 LeetCode 606. Construct String from Binary Tree You need to construct a string consists of parenthesis and integers from a binary tree with the preorder t...

    mikyou 評論0 收藏0

  • [LeetCode] 606. Construct String from Binary Tree

    Problem You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way. The null node needs to be represented by empty parenthesis pair (). And...

    madthumb 評論0 收藏0

  • [LintCode/LeetCode] Construct Binary Tree from Tr

    摘要：做了幾道二分法的題目練手，發(fā)現(xiàn)這道題已經(jīng)淡忘了，記錄一下。這道題目的要點在于找的區(qū)間。邊界條件需要注意若或數(shù)組為空，返回空當前進到超出末位，或超過，返回空每次創(chuàng)建完根節(jié)點之后，要將加，才能進行遞歸。 Construct Binary Tree from Inorder and Preorder Traversal Problem Given preorder and inorder t...

    馬忠志 評論0 收藏0

  • [Leetcode] Construct Binary Tree from Traversal 根據(jù)

    摘要：二分法復雜度時間空間思路我們先考察先序遍歷序列和中序遍歷序列的特點。對于中序遍歷序列，根在中間部分，從根的地方分割，前半部分是根的左子樹，后半部分是根的右子樹。 Construct Binary Tree from Preorder and Inorder Traversal Given preorder and inorder traversal of a tree, constru...

    caoym 評論0 收藏0

  • 前端 | 每天一個 LeetCode

    摘要：在線網(wǎng)站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。 這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

    張漢慶 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<