Open underwindfall opened 2 years ago
https://leetcode-cn.com/problems/construct-string-from-binary-tree/
思路
[ ] 刷15mins
[ ] 刷5mins
// time O(n+m) // space O(n) public String tree2str(TreeNode root) { if (root == null) { return ""; } String res, left, right; left = tree2str(root.left); right = tree2str(root.right); if (left.equals("") && right.equals("")) { res = String.valueOf(root.val); } else if (!left.equals("") && right.equals("")) { res = String.valueOf(root.val) + "(" + left + ")"; } else if (left.equals("") && !right.equals("")) { res = String.valueOf(root.val) + "()" + "(" + right + ")"; } else { res = String.valueOf(root.val) + "(" + left + ")" + "(" + right + ")"; } return res; } // time O(n+m) // space O(n) class Iterative { public String tree2str(TreeNode root) { StringBuilder sb = new StringBuilder(); Set<TreeNode> vis = new HashSet<>(); Deque<TreeNode> d = new ArrayDeque<>(); d.addLast(root); while (!d.isEmpty()) { TreeNode t = d.pollLast(); if (vis.contains(t)) { sb.append(")"); } else { d.addLast(t); sb.append("("); sb.append(t.val); if (t.right != null) d.addLast(t.right); if (t.left != null) d.addLast(t.left); else if (t.right != null) sb.append("("); vis.add(t); } } return sb.substring(1, sb.length() - 1); } }
https://leetcode-cn.com/problems/construct-string-from-binary-tree/
思路
[ ] 刷15mins
[ ] 刷5mins