二叉树中和为某一值的路径.md

题目描述

输入一颗二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下直到 叶节点 所经过的节点形成一条路径。二叉树节点的定义如下：

public class BinaryTreeNode {
    int value;
    BinaryTreeNode left;
    BinaryTreeNode right;
}

测试用例

• 功能测试（二叉树中有一条、多条符合要求的路径；二叉树中没有符合要求的路径）
• 特殊输入测试（指向二叉树根节点的指针是空指针）

题目考点

• 考察应聘者用例子分析复杂问题的能力。
• 考察应聘者对二叉树前序遍历的理解。

解题思路

对于从节点开始的题目，我们需要想到先序遍历。

1. 当用前序遍历的方式访问到某一节点时，就把该节点添加到路径数组中。
2. 如果是叶节点且刚好是我们想要的数，则将它的路径保存起来一份。
3. 如果当前节点不是叶节点，则继续访问它的子节点。
4. 当递归函数退出的时候会返回到它的父节点，所以我们需要在删除路径数组的最后一个节点。

自己解题

只是想到用栈，却不知道模拟栈。

参考解题

/**
 * 二叉树中和为某一值的路径
 *
 * @Author rex
 * 2018/8/9
 */
public class Solution {
    /**
     * 参考解题
     *
     * 例子分析
     * @param root
     * @param target
     * @return
     */
    public ArrayList<ArrayList<Integer>> findPath(BinaryTreeNode root, int target) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        ArrayList<Integer> singleResult = new ArrayList<>();
        if (root == null) {
            return result;
        }
        findPath(root, target, result, singleResult);
        return result;

    }

    public void findPath(BinaryTreeNode node, int target, ArrayList<ArrayList<Integer>>  result, ArrayList<Integer> singleResult) {
        target -= node.value;
        singleResult.add(node.value);
        // 判断是否等于目标值且是叶节点
        if (target == 0 && node.left == null && node.right == null) {
            result.add(new ArrayList<>(singleResult));
        }
        if (node.left != null) {
            findPath(node.left, target, result, singleResult);
        }
        if (node.right != null) {
            findPath(node.right, target, result, singleResult);
        }
        // 删除当前节点的值
        singleResult.remove(singleResult.size()-1);

    }
}