Share my Java solution, generate parentheses by traversing a tree


  • 0
    M

    Emulate the 'drawing parentheses' process by making leftv, rightv be the number of '(' and ')' we currently have.

    class TreeNode {
        int leftv = 0;
        int rightv = 0;
        TreeNode left,right;
        TreeNode(int l, int r) {leftv = l; rightv = r; left = null; right = null;};
    }
    class GenerateParentheses {
        public List<String> generateParenthesis(int n) {
            return traverseTree(constructTree(n));
        }
        private TreeNode constructTree(int n) {
            return construct(n, n);
        }
        private TreeNode construct(int l, int r) {
            TreeNode root = new TreeNode(l, r);
            if (l > 0) root.left = construct(l-1, r);
            if (r > l) root.right = construct(l, r-1);
            return root;
        }
        private List<String> traverseTree(TreeNode node) {
            List<String> result = new ArrayList<String>();
            if (node == null) return result;
            if (node.leftv == 0) {
                StringBuilder sb = new StringBuilder();
                for (int i=0; i< node.rightv; ++i) {
                    sb.append(")");
                }
                result.add(sb.toString());
                return result;
            }
            for (String s: traverseTree(node.left)) {
                result.add("(" + s);
            }
            for (String s: traverseTree(node.right)) {
                result.add(")" + s);
            }
            return result;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.