By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

1、二叉树的所有路径_1

说明: 叶子节点是指没有子节点的节点。

示例：


给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9  20
/  \
15   7


返回它的最大路径和 [[3,9,15],[3,20,7]]

1.1、解题思路

和路径之和解法一样

1.2、算法

public List<List<Integer>> collectTree(TreeNode treeNode){
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> linkedList = new LinkedList<>();
    dfs(treeNode, res, linkedList);
    return res ;
}

public void dfs(TreeNode treeNode, List<List<Integer>> res, LinkedList<Integer> linkedList) {
    if (treeNode == null) {
        return;
    }

    linkedList.add(treeNode.val);
    if (treeNode.right == null || treeNode.left == null) {
        res.add(new ArrayList<>(linkedList));
    }
    if (treeNode.left != null) {
        dfs(treeNode.left, res, linkedList);
        linkedList.removeLast();
    }
    if (treeNode.right != null) {
        dfs(treeNode.right, res, linkedList);
        linkedList.removeLast();
    }
}

1.3、测试


@Test
public void test(){
    System.out.println(collectTree(initTreeNode()));
}

public List<List<Integer>> collectTree(TreeNode treeNode){
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> linkedList = new LinkedList<>();
    dfs(treeNode, res, linkedList);
    return res ;
}





public TreeNode initTreeNode(){
    TreeNode treeNode1 = new TreeNode(3, null ,null);
    TreeNode treeNode2 = new TreeNode(6, null , null);
    TreeNode treeNode3 = new TreeNode(4, treeNode1, treeNode2);
    TreeNode treeNode4 = new TreeNode(1, null, null);
    TreeNode root = new TreeNode(5, treeNode3, treeNode4);
    return root ;
}

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

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

    }
}

1、二叉树的所有路径_2

说明: 叶子节点是指没有子节点的节点。

示例：

 示例:
     输入:
     1
     /   \
     2     3
     \
     5
输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

1.1、解题思路

和路径之和解法一样

1.2、算法

public List<String> binaryTreePaths(TreeNode root) {

    List<String> res = new ArrayList<>();
    dfs(root, res, "");
    return res ;
}

/** 所有的都会走一遍 有点类似于路径总和1 */
public void dfs(TreeNode root, List<String> res , String path) {
    if (root == null){
        return;
    }
    if (root.left == null && root.right == null){
        res.add(path + root.val);
        return;
    }

    //如果不是叶子节点，在分别遍历他的左右子节点
    dfs(root.left, res, path + root.val + "->");
    dfs(root.right, res, path + root.val + "->");
}

1.3、测试

@Test
public void test(){
    System.out.println(binaryTreePaths(initTreeNode()));
}

public TreeNode initTreeNode(){
    TreeNode treeNode1 = new TreeNode(3, null ,null);
    TreeNode treeNode2 = new TreeNode(6, null , null);
    TreeNode treeNode3 = new TreeNode(4, treeNode1, treeNode2);
    TreeNode treeNode4 = new TreeNode(1, null, null);
    TreeNode root = new TreeNode(5, treeNode3, treeNode4);
    return root ;
}

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

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

    }
}

​

ContactAuthor