JAVA understandable preorder apporach using two stacks without using static index


  • 0
    L

    One stack is used to record the TreeNode, and another is used to indicate whether left-child of related node in the nodeStk is already filled:

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();    
        helperS(root, sb);
        return sb.toString();
    }
    private void helperS(TreeNode node, StringBuilder sb){
        if(node == null){
            sb.append("null").append(",");
            return;
        }
        sb.append(node.val).append(",");
        helperS(node.left, sb);
        helperS(node.right, sb);
    }
    
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] vals  = data.split(",");
        Deque<TreeNode> nodeStk = new LinkedList<>();
        Deque<Boolean> leftOrRightStk = new LinkedList<>();
        TreeNode tmp = null;
        for (int idx = 0; idx < vals.length; idx++) {
            String nextVal = vals[idx];
            if (nextVal.equals("null")) {
                if (!leftOrRightStk.isEmpty() && leftOrRightStk.peek() == false) {
                    leftOrRightStk.pop();
                    leftOrRightStk.push(true);
                } else {
                    tmp = null;
                    while (!leftOrRightStk.isEmpty() && leftOrRightStk.peek() == true) {
                        nodeStk.peek().right = tmp;
                        tmp = nodeStk.pop();
                        leftOrRightStk.pop();
                    }
                    if (!leftOrRightStk.isEmpty()) {
                        nodeStk.peek().left = tmp;
                        leftOrRightStk.pop();
                        leftOrRightStk.push(true);
                    }
                }
            } else {
                nodeStk.push(new TreeNode(Integer.parseInt(nextVal)));
                leftOrRightStk.push(false);
            }
        }
        return tmp;
    }

Log in to reply
 

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