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:

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

 

 有括号对还是要加q

不用q的做法,就会要多引入变量,有点麻烦:https://leetcode.com/problems/construct-binary-tree-from-string/discuss/100355/Java-Recursive-Solution

用q的做法:https://leetcode.com/problems/construct-binary-tree-from-string/discuss/100359/Java-stack-solution

public class Solution {
    public TreeNode str2tree(String s) {
        Stack<TreeNode> stack = new Stack<>();
        for(int i = 0, j = i; i < s.length(); i++, j = i){
            char c = s.charAt(i);
       //节点加完了,就pop出来 
if(c == ‘)‘) stack.pop(); else if(c >= ‘0‘ && c <= ‘9‘ || c == ‘-‘){ while(i + 1 < s.length() && s.charAt(i + 1) >= ‘0‘ && s.charAt(i + 1) <= ‘9‘) i++; TreeNode currentNode = new TreeNode(Integer.valueOf(s.substring(j, i + 1))); if(!stack.isEmpty()){ TreeNode parent = stack.peek(); if(parent.left != null) parent.right = currentNode; else parent.left = currentNode; }
          //是数字就加节点 stack.push(currentNode); } }
return stack.isEmpty() ? null : stack.peek(); } }

 

536. Construct Binary Tree from String 从括号字符串中构建二叉树

上一篇:AoiAWD 设置


下一篇:笛卡尔树