Pocket Gems - Ternary Expression to Binary Tree

Pocket Gems - Ternary Expression to Binary Tree - - 博客频道 - CSDN.NET

I came across this problem that has Ternary expression (a?b:c) and needs the ternary expression to be converted into a Binary tree structure.

     a?b:c 

       a
      / \
     b   c

  a?b?c:d:e

     a
    / \
   b   e
  / \
 c   d

http://stackoverflow.com/questions/28487831/how-to-convert-a-ternary-expression-to-a-binary-tree-structure
http://yuanhsh.iteye.com/blog/2206191

1. public TreeNode convertToBT (char[] values) {  
2.     TreeNode root = new TreeNode(values[0]);  
3.     TreeNode n = root;  
4.     Stack<TreeNode> a =  new Stack<TreeNode>();  
5.     for (int i = 1; i < values.length; i += 2) {  
6.         if (values[i] == '?') {  
7.             n.left = new TreeNode (values[i + 1]);  
8.             a.add(n);  
9.             n = n.left;  
10.   
11.         }  
12.         else if (values[i] == ':') {  
13.             n = a.pop();  
14.             while (n.right != null) {  
15.                 n = a.pop();  
16.             }               
17.             n.right = new TreeNode (values[i + 1]);  
18.             a.add(n);  
19.             n = n.right;  
20.         }  
21.     }  
22.     return root;  
23. }  

https://leetcode.com/discuss/66620/ternary-expression-to-binary-tree

Let's assume the input ternary expression is valid, we can build the tree in preorder manner.

Each time we scan two characters, the first character is either ? or :, the second character holds the value of the tree node. When we see ?, we add the new node to left. When we see:, we need to find out the ancestor node that doesn't have a right node, and make the new node as its right child.

Time complexity is O(n).

public TreeNode convert(char[] expr) {
  if (expr.length == 0) {
    return null;
  }

  TreeNode root = new TreeNode(expr[0]);

  Stack<TreeNode> stack = new Stack<>();

  for (int i = 1; i < expr.length; i += 2) {
    TreeNode node = new TreeNode(expr[i + 1]);

    if (expr[i] == '?') {
      stack.peek().left = node;
    }

    if (expr[i] == ':') {
      stack.pop();
      while (stack.peek().right != null) {
        stack.pop();
      }
      stack.peek().right = node;
    }

    stack.push(node);
  }

  return root;
}

https://discuss.leetcode.com/topic/108/convert-a-ternary-expression-to-a-tree/2
Each time I find ''?" I create new left child of currect root, when I find ":" I move the pointer to then next character.

private int pos = 1;
void createTree(String expr, TreeNode root) {
 if  (pos  ==  expr.length())
   return;
 if (expr.charAt(pos) == ':') 
  pos++;
 else {
     if (expr.charAt(pos) == '?') {
      root.left = new TreeNode(expr.charAt(pos +1));
      pos += 2;
      createTree(expr, root.left);
     }  
            if((expr.charAt(pos) != ':') && (expr.charAt(pos) != '?')) 
    {
            root.right = new TreeNode(expr.charAt(pos));
            pos += 1;
            createTree(expr,root.right);
     } 
   }
}

 TreeNode root = new TreeNode('a');
 createTree("a?b?c?d:k:l?m:h?a:s:i",root);

https://github.com/interviewcoder/leetcode/blob/master/src/s09_ConvertTernaryExpressionToBinaryTree/Solution.java
* 1. Does node have parent pointer?
* 2. Expression's format, leading, trailing spaces, spaces between characters?
* 3. May expression be illegal?
* 4. Token's length is always 1?

https://jiangchengl.wordpress.com/2015/07/30/build-a-binary-tree-from-a-ternary-expression/

Read full article from Pocket Gems - Ternary Expression to Binary Tree - - 博客频道 - CSDN.NET