LeetCode 536. Construct Binary Tree from String 从带

tabalt 发布于2019-08-16 13:31 / 2511人阅读

摘要：题意从一个带括号的字符串，构建一颗二叉树。其中当而时，展示为一个空的括号。同时要考虑负数的情况，所以在取数字的时候，必须注意所在位置。遇到则从栈中出元素。最后中的元素就是，返回栈顶元素即可。

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:

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

题意：从一个带括号的字符串，构建一颗二叉树。

解题思路：本题仔细看字符串可以发现，每个root,left,right都是以root.val(left.val)(right.val)展示的。其中当left = null而right != null时，left展示为一个空的括号"()"。同时要考虑负数的情况，所以在取数字的时候，必须注意index所在位置。我们用一个stack存储当前构建好的TreeNode,每次遇到数字时，将数字构建成TreeNode,查看是否为stack为空，不为空，则查看stack中顶层元素的左子树是否已经有了，如果没有，那当前新构建的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();

专线服务私有云 binary-tree LeetCode_String binary-search-tree Construct

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/71883.html

LeetCode 606. Construct String from Binary Tree 二叉

摘要：题意从一颗二叉树转为带括号的字符串。这题是的姊妹题型，该题目的解法在这里解法。 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 2019-08-16 13:31 评论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 2019-08-16 13:39 评论0 收藏0
[LintCode/LeetCode] Construct Binary Tree from Tr

摘要：做了几道二分法的题目练手，发现这道题已经淡忘了，记录一下。这道题目的要点在于找的区间。边界条件需要注意若或数组为空，返回空当前进到超出末位，或超过，返回空每次创建完根节点之后，要将加，才能进行递归。 Construct Binary Tree from Inorder and Preorder Traversal Problem Given preorder and inorder t...

马忠志 2019-08-14 15:40 评论0 收藏0
[Leetcode] Construct Binary Tree from Traversal 根据

摘要：二分法复杂度时间空间思路我们先考察先序遍历序列和中序遍历序列的特点。对于中序遍历序列，根在中间部分，从根的地方分割，前半部分是根的左子树，后半部分是根的右子树。 Construct Binary Tree from Preorder and Inorder Traversal Given preorder and inorder traversal of a tree, constru...

caoym 2019-08-14 12:32 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0