首页 > 华为笔试 5.6 第三题(部分)根据输入字符串构造树
头像
offer扒拉我
编辑于 2020-05-07 20:29
+ 关注

华为笔试 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(")");
            }
        }
    }
}

更多模拟面试

全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐