Expression Tree Build 367

Question

The structure of Expression Tree is a binary tree to evaluate certain expressions. All leaves of the Expression Tree have an number string value. All non-leaves of the Expression Tree have an operator string value.

Now, given an expression array, build the expression tree of this expression, return the root of this expression tree.

Clarification

See wiki:

Expression Tree

Example

For the expression (26-(23+7)/(1+2)) (which can be represented by ["2" "" "6" "-" "(" "23" "+" "7" ")" "/" "(" "1" "+" "2" ")"]).

The expression tree will be like

             [ - ]
         /          \
    [ * ]              [ / ]
  /     \           /         \
[ 2 ]  [ 6 ]      [ + ]        [ + ]
                 /    \       /      \
               [ 23 ][ 7 ] [ 1 ]   [ 2 ] .

After building the tree, you just need to return root node [-].

Solution

观察example，可以看出所有叶节点都为数字。如果给每个元素赋予一个优先级， 和 ／ 为2， ＋ 和 － 为1， 数字为极大值，然后规定优先级越大的越在下，越小的越在上。这样，这道题就转化为构建*Min Tree，和之前的Max Tree做法类似，只是这里维持的是一个递增栈。同时，当遇见“（”时，提高优先级，遇见“）”时，降低优先级。

1. 遍历数组，给每个新来的元素赋予一个val值用以比较优先级。 * 和 ／ 为2， ＋ 和 － 为1， 数字为极大值。

2. 此时看栈顶元素（若栈为空则直接加入）。为了维持一个递增栈，若栈顶元素比新来元素val大（或相等），则出栈；若栈顶元素比新来元素val小，则break。

3. 若2中栈顶元素出栈，此时若栈为空，则将出栈元素作为新来元素的左节点，并将新来元素加入栈中；若不为空，看新栈顶元素，若新栈顶元素比新来元素val小，则将出栈元素作为新来元素的左孩子，并将新来元素加入栈中；若新栈顶元素比新来元素val大（或相等），则将出栈元素作为新栈顶元素的右节点，重复2-3，直到栈为空或者栈顶元素比新来元素要小，将新来元素加入栈中。

4. tips：在遍历万整个数组后，多加一个值，将其val赋值为极小，这样所有元素都会出栈并构建成完整的树。

代码如下：

/**
 * Definition of ExpressionTreeNode:
 * public class ExpressionTreeNode {
 *     public String symbol;
 *     public ExpressionTreeNode left, right;
 *     public ExpressionTreeNode(String symbol) {
 *         this.symbol = symbol;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param expression: A string array
     * @return: The root of expression tree
     */
    class TreeNode{
        int val;
        ExpressionTreeNode root;
        public TreeNode(int val, String s){
            this.val = val;
            root = new ExpressionTreeNode(s);
        }
    }

    public int getPriority(String s, int base){
        if(s.equals("-") || s.equals("+")){
            return 1 + base;
        }
        if(s.equals("*") || s.equals("/")){
            return 2 + base;
        }
        return Integer.MAX_VALUE;
    }

    public ExpressionTreeNode build(String[] expression) {
        // write your code here
        if(expression == null || expression.length == 0){
            return null;
        }

        int val = 0;
        int base = 0;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        for(int i = 0; i <= expression.length; i++){
            if(i != expression.length){
                if(expression[i].equals("(")){
                    base += 10;
                    continue;
                }
                if(expression[i].equals(")")){
                    base -= 10;
                    continue;
                }
                val = getPriority(expression[i], base);
            }

            TreeNode right = i == expression.length? new TreeNode(Integer.MIN_VALUE, "") : new TreeNode(val, expression[i]);
            while(!stack.isEmpty()){
                if(stack.peek().val >= right.val){
                    TreeNode nodeNow = stack.pop();
                    if(stack.isEmpty()){
                        right.root.left = nodeNow.root;
                    }else{
                        TreeNode left = stack.peek();
                        if(left.val < right.val){
                            right.root.left = nodeNow.root;
                        }else{
                            left.root.right = nodeNow.root;
                        }
                    }
                }else{
                    break;
                }
            }
            stack.push(right);
        }

        return stack.peek().root.left;
    }
}

Related Question

Max Tree 126