LeetCode Construct String from Binary Tree
原题链接在这里：https://leetcode.com/problems/construct-string-from-binary-tree/#/description
题目：
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]
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]
1
/ \
2 3
\
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.
题解：
类似Binary Tree Preorder Traversal.
Method 1时recursion方法. 但要注意几种特殊情况：
在left child, right child 都是null的情况下是不iterate child 的
如果left child 和right child 中至少有一个不是null 就iterate child 此时无论left child 是否为null 都需要 iterate
在右侧child 不为null时才iterate.
Time Complexity: O(n). 每个节点走了一遍. Space: O(logn), stack space.
AC Java:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public String tree2str(TreeNode t) {
StringBuilder sb = new StringBuilder();
preorderTraversal(t, sb);
return sb.toString();
} private void preorderTraversal(TreeNode t, StringBuilder sb){
if(t == null){
return;
} sb.append(t.val);
if(t.left == null && t.right == null){
return;
} // 到此说明左右child至少有一个不是null 那么就要iterate left child
sb.append("(");
preorderTraversal(t.left, sb);
sb.append(")"); // right child在不是null时才会iterate
if(t.right != null){
sb.append("(");
preorderTraversal(t.right, sb);
sb.append(")");
}
}
}
Method 2是iteration方法. 类似Binary Tree Preorder Traversal的method 2.
多了visited 来标记已经iterate的点. 在peek stack后如果iterate过了就pop stack 并把")"加到结果中.
Time Complexity: O(n). n是节点个数. Space: O(n).
AC Java:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public String tree2str(TreeNode t) {
StringBuilder sb = new StringBuilder();
if(t == null){
return sb.toString();
} Stack<TreeNode> stk = new Stack<TreeNode>();
stk.push(t);
HashSet<TreeNode> visited = new HashSet<TreeNode>();
while(!stk.isEmpty()){
TreeNode tn = stk.peek();
if(visited.contains(tn)){
stk.pop();
sb.append(")");
}else{
visited.add(tn);
sb.append("(" + tn.val);
if(tn.left==null && tn.right!=null){
sb.append("()");
}
if(tn.right != null){
stk.push(tn.right);
}
if(tn.left != null){
stk.push(tn.left);
}
}
}
return sb.toString().substring(1,sb.length()-1);
}
}
跟上Construct Binary Tree from String.
最新文章
- Oracle数据库找回密码
- 同感，C#对JSON序列化和反序列化有点蹩脚
- Dynamics AX 2012 R2 AIF 内部异常 output session was auto-closes
- python学习09——字典（3）
- Java--Semaphore控制并发线程数量
- 如何根据IP查找计算机名
- mysql之sql语句导入与导出讲解
- linux - 开机启动thunderbird、chromium
- CString 与 std::string 相互转化
- docker rancher 体验 (未完待续.....)
- PHP运算符与表达式
- 【开发技术】Get请求和Post请求区别
- spring 纯注解方式 与AOP
- C++：位操作基础篇之位操作全面总结
- java实现四则运算
- 自学Linux Shell9.4-基于Red Hat系统工具包存在两种方式之二：源码包
- pitch, yaw, roll
- 高级openg 混合，一个完整程序
- OpenCV——LBP(Local Binary Patterns)特征检测
- Surrounded Regions leetcode java