JavaC++题解与拓展——leetcode606.根据二叉树创建字符串【HashSet，ArrayDeque，unordered

本文主要是介绍JavaC++题解与拓展——leetcode606.根据二叉树创建字符串【HashSet，ArrayDeque，unordered_set学习与使用】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

每日一题做题记录，参考官方和三叶的题解

题目要求

在这里插入图片描述
注：当节点仅有一个子树，右子树为空需去除冗余括号，左子树为空需添加一对括号。

思路一：递归

题目是输出树的前序遍历结果的变体形式（给每个子树加括号），所以可以使用深度优先遍历进行递归解决。
下文采用两种表达形式，Java中将DFS另外定义，C++直接调用自己，前者方法更具有“树”类题目的普适性，后者更明了不容易落下括号。（不是因为C++字符串不好修改才不一样的）

Java

class Solution {StringBuilder res = new StringBuilder();public String tree2str(TreeNode root) {DFS(root);return res.substring(1, res.length() - 1); //忽略首尾括号}void DFS(TreeNode root) {res.append("(");res.append(root.val);if (root.left != null)DFS(root.left);else if (root.right != null) //左空右不空res.append("()"); //指代空的左子树if (root.right != null)DFS(root.right);res.append(")");        }
}

时间复杂度：O(m + n)，m为边数，n为节点数
空间复杂度：O(n)

C++

class Solution {
public:string tree2str(TreeNode *root) {if (root == nullptr)return "";if (root->left == nullptr && root->right == nullptr) //叶子return to_string(root->val);if (root->right == nullptr) //右子树空则跳过，以防止产生冗余括号return to_string(root->val) + "(" + tree2str(root->left) + ")";return to_string(root->val) + "(" + tree2str(root->left) + ")(" + tree2str(root->right) + ")";}
};

时间复杂度：O(n)，n为节点数
空间复杂度：O(n)

思路二：迭代（用栈替代递归）

定义一个栈存，栈底到栈顶依次存根到当前节点的经过的节点，将其依次加入结果并添加括号，因此还需一个额外的集合存储已遍历（输出）过的节点。未遍历过则添加“（”和该节点并向下遍历其子树，遍历过则添加“）”。

Java

class Solution {public String tree2str(TreeNode root) {StringBuilder res = new StringBuilder();Set<TreeNode> vis = new HashSet<>(); //是否遍历过Deque<TreeNode> stack = new ArrayDeque<>(); //基于双端队列创建栈stack.addLast(root);while (!stack.isEmpty()) {TreeNode t = stack.pollLast();if (vis.contains(t)) //遍历过res.append(")");else {stack.addLast(t);res.append("(");res.append(t.val);//先进后出，所以先压入右子树内容if (t.right != null)stack.addLast(t.right);if (t.left != null)stack.addLast(t.left);else if (t.right != null)res.append("()");vis.add(t);}}return res.substring(1, res.length() - 1); //忽略首尾冗余括号}
}

时间复杂度：O(m + n)，m为边数，n为节点数
空间复杂度：O(n)

HashSet

学习参考链接
简介
- 基于HashMap实现，元素不可重复，但可有空值；
- 不会对插入数据排序。

方法	功能
contains(key)	判断key是否存在于容器中
add(key)	将key加入容器

ArrayDeque

学习参考链接
简介
- 一个两端皆可插入/删除的队列

方法	功能
addLast(key)	将key加入队尾
isEmpty()	队列是否为空
pollLast(key)	返回并删除队尾元素key

C++

class Solution {
public:string tree2str(TreeNode* root) {string res = "";stack<TreeNode *> st;st.push(root);unordered_set<TreeNode *> vis;while(!st.empty()) {auto node = st.top();if(vis.count(node)) {if(node != root)res += ")";st.pop();}else {vis.insert(node);if(node != root)res += "(";res += to_string(node -> val);if(node -> left == nullptr && node -> right != nullptr)res += "()"; //顶替空的左子树if(node -> right != nullptr)st.push(node -> right);if(node -> left != nullptr)st.push(node -> left);}}return res;}
};