题目描述

根据给定的二叉树结构描述字符串，输出该二叉树按照中序遍历结果字符串。中序遍历顺序为:左子树，根结点，右子树。

输入描述
由大小写字母、左右大括号、逗号组成的字符串:
1、字母代表一个节点值，左右括号内包含该节点的子节点。
2、左右子节点使用逗号分隔，逗号前为空则表示左子节点为空,没有逗号则表示右子节点
为空。
3、二叉树节点数最大不超过100。
注:输入字符串格式是正确的，无需考虑格式错误的情况。

输出描述
输出一个字符串，为二叉树中序遍历各节点值的拼接结果。

示例：
输入：a{b{d, e{g,h{,I}}},c{f}｝
输出：dbgehiafc

代码实现

import java.util.*;

public class Test {

    public static class TreeNode {
        String val;
        TreeNode left;
        TreeNode right;
        TreeNode parent;
    }

    public static void main(String[] args) {
        String str = "a{b{d,e{g,h{,I}}},c{f}}";

        TreeNode root = new TreeNode();
        //当前节点
        TreeNode current = root;
        //是否左节点为空
        boolean leftIsNull = true;
        String val = "";
        //0表示根节点，1表示左子树，2表示右子树
        int direction = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '{'){
                //左子树
                direction = 1;
                leftIsNull = true;
            }else if (str.charAt(i) == ','){
                //右子树
                direction = 2;
            }else if (str.charAt(i) == '}'){
                current = current.parent;
            }else {
                if (direction == 0){
                    val = String.valueOf(str.charAt(i));
                    current.val = val;
                }else if (direction == 1){
                    val = String.valueOf(str.charAt(i));
                    current.left = new TreeNode();
                    current.left.parent = current;
                    current.left.val = val;
                    current = current.left;
                    leftIsNull = false;
                }else if (direction == 2){
                    val = String.valueOf(str.charAt(i));
                    //左节点不为空说明当前节点指向左节点，否则指向根节点
                    if (!leftIsNull){
                        current.parent.right = new TreeNode();
                        current.parent.right.parent = current.parent;
                        current.parent.right.val = val;
                        current = current.parent.right;
                    }else {
                        current.right = new TreeNode();
                        current.right.parent = current;
                        current.right.val = val;
                        current = current.right;
                    }
                    leftIsNull = false;

                }
            }
        }

        List<String> list = new ArrayList<>();
        inOrder(root,list);
        for (String s : list) {
            System.out.print(s);
        }
    }

    public static void inOrder(TreeNode root, List<String> list){
        if (root == null){
            return;
        }
        inOrder(root.left,list);
        list.add(root.val);
        inOrder(root.right,list);
    }

}