脚本宝典收集整理的这篇文章主要介绍了LeetCode 536. Construct Binary Tree from String 从带括号字符串构建二叉树,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
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 ()"
.
题意:从一个带括号的字符串,构建一颗二叉树。
解题思路: 本题仔细看字符串可以发现,每个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<TreeNode> 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();
以上是脚本宝典为你收集整理的LeetCode 536. Construct Binary Tree from String 从带括号字符串构建二叉树全部内容,希望文章能够帮你解决LeetCode 536. Construct Binary Tree from String 从带括号字符串构建二叉树所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。