Max Depth Path

题目：
print max depth path of a binary tree

解题思路：
这道题首先需要找到max depth，然后用一个helper函数将符合要求的list加进去rst里面。

代码：

public class MaxDepthPath {

    public static List<List<Integer>> rst = new ArrayList<>();

    public void getMaxDepthPath(TreeNode root){
        int maxDepth = getMaxDepth(root);
        getPath(root, new ArrayList<>(), maxDepth, 0);
    }

    private void getPath(TreeNode root, List<Integer> list, int maxDepth, int depth) {
        if(root == null){
            return;
        }
        depth++;
        list.add(root.val);
        if(depth == maxDepth){
            rst.add(new ArrayList<>(list));
            return;
        }
        getPath(root.left, new ArrayList<>(list), maxDepth, depth);
        getPath(root.right, new ArrayList<>(list), maxDepth, depth);
    }

    private int getMaxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        return 1 + Math.max(getMaxDepth(root.left), getMaxDepth(root.right));
    }

    public static void main(String[] args){
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);
        TreeNode node9 = new TreeNode(9);
        node5.left = node6;
        node5.right = node7;
        node3.left = node8;
        node3.right = node9;
        node2.left = node4;
        node2.right = node5;
        node1.left = node2;
        node1.right = node3;
        MaxDepthPath maxDepthPath = new MaxDepthPath();
        maxDepthPath.getMaxDepthPath(node1);
        System.out.println(rst);
    }


}