LeetCode 606. Construct String from Binary Tree 二叉

mikyou 发布于2019-08-16 13:31 / 1141人阅读

摘要：题意从一颗二叉树转为带括号的字符串。这题是的姊妹题型，该题目的解法在这里解法。

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 traversing way.

The null node needs to be represented by empty parenthesis pair "()". And you need to omit all the empty parenthesis pairs that don"t affect the one-to-one mapping relationship between the string and the original binary tree.

Example 1:
Input: Binary tree: [1,2,3,4]

Output: "1(2(4))(3)"

Explanation: Originallay it needs to be "1(2(4)())(3()())",
but you need to omit all the unnecessary empty parenthesis pairs.
And it will be "1(2(4))(3)".

Example 2:
Input: Binary tree: [1,2,3,null,4]

Output: "1(2()(4))(3)"

Explanation: Almost the same as the first example,
except we can"t omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.

题意: 从一颗二叉树转为带括号的字符串。这题是LeetCode 536的姊妹题型，该题目的解法在这里LeetCode 536解法。

解题思路：和536一样，这题的括号的位置，字符串的结构为root.val(root.left.val)(root.right.val)，当left为空时，需要多加一个(), 我们循环DFS调用function, 先得到当前的node的value，再得到左子树的字符串，和右子树的字符串，用StringBuilder链接起来，用""来判断是否为空，其中值得注意的是- StringBuilder在初始化一个int值时，需要额外添+""，使得它为一个字符串，而不会解析成capacity。

StringBuilder(int initCapacity)
Creates an empty string builder with the specified initial capacity.

public String tree2str(TreeNode t) {
        if (t == null) {
            return "";
        }
        StringBuilder res = new StringBuilder(t.val+"");
        String left = tree2str(t.left);
        String right = tree2str(t.right);
        if (left.equals("") && right.equals("")) {
            return res.toString();
        }
        if (left.equals("") && !right.equals("")) {
            res.append("()(").append(right).append(")");
            return res.toString();
        }
        if (!left.equals("") && right.equals("")) {
            res.append("(").append(left).append(")");
            return res.toString();
        }
        res.append("(").append(left).append(")").append("(").append(right).append(")");
        return res.toString();
        
    }

GPU云服务器云服务器 binary-tree LeetCode_String binary-search-tree Construct

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

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

[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
前端 | 每天一个 LeetCode

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

张汉庆 2019-08-23 13:42 评论0 收藏0
LeetCode 536. Construct Binary Tree from String 从带

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

tabalt 2019-08-16 13:31 评论0 收藏0
LeetCode 精选TOP面试题【51 ~ 100】

摘要：有效三角形的个数双指针最暴力的方法应该是三重循环枚举三个数字。总结本题和三数之和很像，都是三个数加和为某一个值。所以我们可以使用归并排序来解决这个问题。注意因为归并排序需要递归，所以空间复杂度为 ...

Clect 2021-11-15 11:38 评论0 收藏0
leetcode-106-根据中序和后序遍历，构造二叉树

摘要：题目描述以为中心进行分类题目分析根据中序和后序遍历，构造二叉树。根据动态规划方法，找出循环的共性。构造子二叉树，需要节点，和左右连接，从后序遍历找出根节点，从对目标序列进行切分，如此往复。题目描述： Given inorder and postorder traversal of a tree, construct the binary tree. Note: You may a...

widuu 2019-07-30 16:04 评论0 收藏0