内容简介：给予一颗二叉树，根据前序遍历构建一个字符串, 不过需要在每个元素和他的子元素的外层用例 :采用深度优先遍历, 需要注意特殊情况: 当一个节点有左子树, 但没有右子树时, 可以省略右子树的
给予一颗二叉树，根据前序遍历构建一个字符串, 不过需要在每个元素和他的子元素的外层用 ()
包住, 并且需要你不会影响字符串和原始二叉树之间一一对应关系的空括号对.
例 :
给予树：
1
/ \
2 3
/
4
全部返回应该是: `1(2(4)())(3()())`.
省略掉不必要的括号对后的结果为: `1(2(4))(3)`.
给予树：
1
/ \
2 3
\
4
返回: "1(2()(4))(3)"
解法
采用深度优先遍历, 需要注意特殊情况: 当一个节点有左子树, 但没有右子树时, 可以省略右子树的 ()
. 当一个节点有右子树, 但没有左子树, 就不能省略左子树的 ()
.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public String tree2str(TreeNode t) {
if (t == null) {
return "";
}
if (t.left == null && t.right == null) {
return t.val + "";
} else if (t.left != null && t.right != null) {
return t.val + "(" + tree2str(t.left) + ")" + "(" + tree2str(t.right) + ")";
} else if (t.left != null) {
return t.val + "(" + tree2str(t.left) + ")";
} else {
return t.val + "()(" + tree2str(t.right) + ")";
}
}
}
Runtime: 6 ms, faster than 84.71% of Java online submissions for Construct String from Binary Tree. Memory Usage: 37.6 MB, less than 98.36% of Java online submissions for Construct String from Binary Tree.
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
- LeetCode 606 Construct String from Binary Tree
- Leetcode PHP题解--D92 606. Construct String from Binary Tree
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
