606. Construct String from Binary Tree - Easy
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)" ? Example 2: Input: Binary tree: [1,null,4] 1 / 2 3 4 Output: "1(2()(4))(3)" ? 分4种情况考虑: 1. 左右子节点都没有,不加() 2. 左右子节点都有,不加() 3. 只有左子节点,不加() 4. 只有右子节点,加() time: O(n),space: O(height) /** * 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 Integer.toString(t.val); } if(t.right == null) { return t.val + "(" + tree2str(t.left) + ")" + tree2str(t.right); } return t.val + "(" + tree2str(t.left) + ")" + "(" + tree2str(t.right) + ")"; } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |