华为笔试 5.6 第三题（部分）根据输入字符串构造树

第三题：给一个二叉树，然后计算树的最大路径；二叉树举例：1(2,3(4,5)) ： 1是根，2和3是叶子，然后3又有4，5叶子。

感觉最难的就是构造树了，就写了一个（本人java菜鸡，你懂的）
后面的求最大路段和的没有写

• 提取出输入字符串中所有的数字

  Scanner s = new Scanner(System.in);
  String line = s.nextLine();
  //        if(line.equals("")){
  //            System.out.println(0);
  //        }
  List<String> lineNumsList = Arrays.asList(line.split(",|\\(|\\)"));
  List<String> lineNums = new ArrayList<>(lineNumsList);
  Iterator<String> it = lineNums.iterator();
  while (it.hasNext()){
    if(it.next().equals("")){
        it.remove();
    }
  }
  int[] nums = new int[lineNums.size()];
  for (int i = 0; i < lineNums.size(); i++) {
    nums[i] = Integer.parseInt(lineNums.get(i));
  }

• 构造树

  • 栈中保存父节点
  • 遇到 ( ,说明该节点为父节点，压栈
  • 遇到 , ,说明 , 后面的数栈顶的父节点的右子树，出栈

/**
 * 根据输入构造树
 * @param line  原始输入的字符串
 * @param nums  字符串中的所有数字
 * @return  返回树的根节点
 */
private static TreeNode constructTree(String line, int[] nums) {
    Stack<TreeNode> parents = new Stack<>();
    TreeNode root = new TreeNode(nums[0]);

    int numIndex = 1;
    char[] lineChar = line.toCharArray();
    TreeNode node = root;
    for (int i = 0; i < lineChar.length&&numIndex<nums.length; i++) {
        if(lineChar[i] == '('){
            parents.push(node);// 该节点为父节点
            if(lineChar[i+1]!=','){
                node.left = new TreeNode(nums[numIndex++]);
                node = node.left;
            }else{// 左子树为空
                node.left=null;
                i++;
            }
        }if(lineChar[i] == ','){// 取出栈中的父节点
            node = parents.pop();
            if(lineChar[i+1]!=')'){
                node.right = new TreeNode(nums[numIndex++]);
//                    System.out.println(node.val+" .right " + node.right.val);
                node = node.right;
            }else{// 右子树为空
                node.right = null;
                i++;
            }
        }
    }

    return root;
}


- 完整代码
```java
import java.util.*;

/**
 * 华为5.6 机试第三题
 * 根据字符串构造树
 * 测试：
 * -1(3,2)
 * 1(2(4,5),3(,5))
 * 1(2(4,6(2,7)),3(,5))
 */
public class Main {
    static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val, TreeNode left, TreeNode right){
            this.val = val;
            this.left = left;
            this.right = right;
        }
        public TreeNode(int val){
            this(val, null, null);
        }
    }
    public static void main(String[] args) {
        // 构造树
        Scanner s = new Scanner(System.in);
        String line = s.nextLine();
//        if(line.equals("")){
//            System.out.println(0);
//        }
        List<String> lineNumsList = Arrays.asList(line.split(",|\\(|\\)"));
        List<String> lineNums = new ArrayList<>(lineNumsList);
        Iterator<String> it = lineNums.iterator();
        while (it.hasNext()){
            if(it.next().equals("")){
                it.remove();
            }
        }
        int[] nums = new int[lineNums.size()];
        for (int i = 0; i < lineNums.size(); i++) {
            nums[i] = Integer.parseInt(lineNums.get(i));
        }
        // 构造树
        TreeNode root = constructTree(line, nums);
        // 先序遍历验证一下一下
        System.out.println("--------先序验证--------");
        StringBuilder sb = new StringBuilder();
        preOrder(root, sb);
        System.out.println(sb.toString());
    }

    /**
     * 根据输入构造树
     * @param line  原始输入的字符串
     * @param nums  字符串中的所有数字
     * @return  返回树的根节点
     */
    private static TreeNode constructTree(String line, int[] nums) {
        Stack<TreeNode> parents = new Stack<>();
        TreeNode root = new TreeNode(nums[0]);

        int numIndex = 1;
        char[] lineChar = line.toCharArray();
        TreeNode node = root;
        for (int i = 0; i < lineChar.length&&numIndex<nums.length; i++) {
            if(lineChar[i] == '('){
                parents.push(node);// 该节点为父节点
                if(lineChar[i+1]!=','){
                    node.left = new TreeNode(nums[numIndex++]);
                    node = node.left;
                }else{// 左子树为空
                    node.left=null;
                    i++;
                }
            }if(lineChar[i] == ','){// 取出栈中的父节点
                node = parents.pop();
                if(lineChar[i+1]!=')'){
                    node.right = new TreeNode(nums[numIndex++]);
//                    System.out.println(node.val+" .right " + node.right.val);
                    node = node.right;
                }else{// 右子树为空
                    node.right = null;
                    i++;
                }
            }
        }

        return root;
    }

    /**
     * 先序遍历验证树结构
     * @param node  树节点
     * @param sb    StringBuilder
     */
    private static void preOrder(TreeNode node, StringBuilder sb) {
        if (node!=null){
            sb.append(node.val);
            if(node.left!=null){
                sb.append("(");
                preOrder(node.left, sb);
            }else if(node.right!=null){
                sb.append("(");
            };
            if(node.right!=null){
                sb.append(",");
                preOrder(node.right, sb);
                sb.append(")");
            }
        }
    }
}