LeetCode 从str输入构建树 java

LeetCode 从str输入构建树 java

buildTreeFromListStr

package leetcode.t113;

import java.util.*;
import java.util.stream.Collectors;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}


class Solution {
    int targetSum;
    List> pathes = new ArrayList<>();
    void dfs(TreeNode node, int nowSum, List path) {
        if (node == null) {
            //if (nowSum == targetSum) {
            //    pathes.add(path);
            //}
            return;
        }
        //走过了会重复走嘛
        nowSum += node.val;
        path.add(node.val);

        System.out.println("=======");
        System.out.println("node.val");
        System.out.println(node.val);

        System.out.println("nowSum");
        System.out.println(nowSum);


        //dfs(node.left);
        //dfs(node.right);

        //dfs(node.left,nowSum);
        //dfs(node.right,nowSum);

        if(node.left==null&&node.right==null&&nowSum==targetSum){
            System.out.println("path");
            System.out.println(path);
            pathes.add(path);
        }
        dfs(node.left, nowSum, path);
        dfs(node.right, nowSum, path);
        path.remove(path.size() - 1);
    }

    //void dfs(TreeNode node, int nowSum, List path) {
    //    if (node == null) {
    //        if (nowSum == targetSum) {
    //            pathes.add(path);
    //        }
    //        return;
    //    }
    //    //走过了会重复走嘛
    //    nowSum += node.val;
    //    path.add(node.val);
    //
    //    System.out.println("=======");
    //    System.out.println("node.val");
    //    System.out.println(node.val);
    //
    //    System.out.println("nowSum");
    //    System.out.println(nowSum);
    //
    //
    //    //dfs(node.left);
    //    //dfs(node.right);
    //
    //    //dfs(node.left,nowSum);
    //    //dfs(node.right,nowSum);
    //
    //    dfs(node.left, nowSum, path);
    //    dfs(node.right, nowSum, path);
    //    path.remove(path.size() - 1);
    //}

    //[5,4,8,11,null,13,4,7,2,null,null,5,1]
    //        22
    //public List> pathSum(TreeNode root, int targetSum) {
    //    this.targetSum = targetSum;
    //    dfs(root, 0, new ArrayList<>());
    //    return pathes;
    //    //return null;
    //}


    //TreeNode createNode(int idx, List nums){
    //
    //}
    //void put(TreeNode node,int val){
    static void putVal(TreeNode node, int idx, List nums) {
        //node.val=val;
        if (idx >= nums.size()) {
            return;
        }
        Integer integer = nums.get(idx);
        if (integer == null) {
            return;
        }
        //node=
        //if(nums.get(idx))
        //if (node == null) {
        //    return;
        //}
        node.val = nums.get(idx);
        if (idx * 2 + 1 >= nums.size()) {
            //return;
            node.left = null;
        } else {
            node.left = new TreeNode();
            //node.left=new TreeNode();
            //node.right=new TreeNode();
            putVal(node.left, idx * 2 + 1, nums);
        }

        if (idx * 2 + 2 >= nums.size()) {
            //return;
            //node.left=null;
            node.right = null;
        } else {
            //node.left=new TreeNode();
            //node.left=new TreeNode();
            node.right = new TreeNode();
            //putVal(node.left, idx * 2 + 1, nums);
            putVal(node.right, idx * 2 + 2, nums);
        }
        //node.left=new TreeNode();
        //node.right=new TreeNode();
        //putVal(node.left, idx * 2 + 1, nums);
        //putVal(node.right, idx * 2 + 2, nums);
    }

    static TreeNode buildTreeFromListStr(String listStr) {
        List list = listStrToNumList(listStr);
        TreeNode treeNode = buildTreeByNumList(list);
        return treeNode;


    }

    static TreeNode buildTreeByNumList(List list) {
        TreeNode root = new TreeNode();
        putVal(root, 0, list);
        return root;

    }

    static List listStrToNumList(String listStr) {
        //String inputStr = "[5,4,8,11,null,13,4,7,2,null,null,5,1]";
        String trim = listStr.replace("[", "").
                replace("]", "").trim();

        List listNums = Arrays.stream(trim.split(",")).map(o -> {
            if (o.equals("null")) {
                return null;
            }
            return Integer.parseInt(o);
        }).collect(Collectors.toList());
        return listNums;
    }

    static void testPutNums() {
        //Listnums=new ArrayList<>();
        TreeNode root = new TreeNode();
        //0*2+1==1
        //0*2+2==2
        //1*2+1==3
        //root.left.val=nums.get(0*2+1);
        //root.right.val=nums.get(0*2+1);
        String inputStr = "[5,4,8,11,null,13,4,7,2,null,null,5,1]";
        String trim = inputStr.replace("[", "").
                replace("]", "").trim();

        List listNums = Arrays.stream(trim.split(",")).map(o -> {
            if (o.equals("null")) {
                return null;
            }
            return Integer.parseInt(o);
        }).collect(Collectors.toList());
        putVal(root, 0, listNums);
        System.out.println(root.val);
        System.out.println(root.left.val);
        System.out.println(root.left.left.val);
    }


    //[5,4,8,11,null,13,4,7,2,null,null,5,1]
    //        22
    public List> pathSum(TreeNode root, int targetSum) {
        this.targetSum = targetSum;
        dfs(root, 0, new ArrayList<>());
        return pathes;
        //return null;
    }



    List> ret = new linkedList>();
    Deque path = new linkedList();

    //public List> pathSum(TreeNode root, int targetSum) {
    //    dfs(root, targetSum);
    //    return ret;
    //}

    public void dfs(TreeNode root, int targetSum) {
        if (root == null) {
            return;
        }
        path.offerLast(root.val);
        targetSum -= root.val;
        if (root.left == null && root.right == null && targetSum == 0) {
            ret.add(new linkedList(path));
        }
        dfs(root.left, targetSum);
        dfs(root.right, targetSum);
        path.pollLast();
    }
    //
    //作者：LeetCode-Solution
    //链接：https://leetcode-cn.com/problems/path-sum-ii/solution/lu-jing-zong-he-ii-by-leetcode-solution/
    //来源：力扣（LeetCode）
    //著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

    void test2() {
        List nums = new ArrayList<>();
        TreeNode root = new TreeNode();
        //0*2+1==1
        //0*2+2==2
        //1*2+1==3
        root.left.val = nums.get(0 * 2 + 1);
        root.right.val = nums.get(0 * 2 + 1);
        String inputStr = "[5,4,8,11,null,13,4,7,2,null,null,5,1]";
        String trim = inputStr.replace("[", "").
                replace("]", "").trim();

        List listNums = Arrays.stream(trim.split(",")).map(o -> {
            if (o.equals("null")) {
                return null;
            }
            return Integer.parseInt(o);
        }).collect(Collectors.toList());
        putVal(root, 0, listNums);

        //https://leetcode-cn.com/problems/path-sum-ii/
        root.val = 3;
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
    }

    static void test3() {
        Solution solution = new Solution();
        TreeNode treeNode =
                buildTreeFromListStr("[5,4,8,11,null,13,4,7,2,null,null,5,1]");
        //List> lists = pathSum(treeNode, 22);
        List> lists = solution.pathSum(treeNode, 22);
        System.out.println("lists");
        System.out.println(lists);
    }

    public static void main(String[] args) {
        //testPutNums();
        test3();
    }
}