题解 | #二叉树中和为某一值的路径(二)#

import java.util.HashMap;
import java.util.Stack;
import java.util.LinkedList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
public class Solution {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
        
        // 定义返回结果集
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        
        if (null == root) {
            return result;
        }
        if (null == root.left && null == root.right) {
            if (root.val == expectNumber) {
                ArrayList<Integer> pr = new ArrayList<>();
                pr.add(root.val);
                result.add(pr);
                return result;
            }
            return result;
        }
        // 具体代码实现
        // 首先，我们要找到这棵树的所有叶子节点，存放到一个队列当中去
        // 定义一个队列，用于存放所有叶子节点
        LinkedList<TreeNode> chn = new LinkedList<>();
        // 定义一个辅助节点
        TreeNode tn = root;
        // 定义一个stack，用于实现前序遍历
        Stack<TreeNode> st = new Stack<>();
        // 初始化
        st.push(tn);
        while (!st.isEmpty()) {
            tn = st.pop();
            if (null == tn.left && null == tn.right) { // 叶子节点
                chn.add(tn);
                continue; // 直接跳过下面的步骤
            }
            if (null != tn.right) {
                st.push(tn.right);
            }
            if (null != tn.left) {
                st.push(tn.left);
            }
        }
        // 循环结束后，我们得到了所有的叶子节点
        tn = root;
        // 同时，我们还想知道每个节点与其父节点的对应关系
        HashMap<TreeNode, TreeNode> ff = FindFather(root);
        while (!chn.isEmpty()) {
            // 定义一个整型变量，用于临时存放数据
            int val = 0;
            // 定义一个栈
            Stack<Integer> s1 = new Stack<>();
            tn = chn.poll();
            while (root != tn) {
                val = val + tn.val;
                s1.push(tn.val);
                tn = ff.get(tn);
            }
            if ((val + root.val) == expectNumber) {
                s1.push(root.val);
                // 该叶子节点到 root 节点的路径
                ArrayList<Integer> pr = new ArrayList<>();
                while (!s1.isEmpty()) {
                    pr.add(s1.pop());
                }
                result.add(pr);
            }
        }
        // 返回最终的结果集
        return result;
    }
    
    
    
    // 该函数用于找到每个节点与其父节点对应的关系
    public static HashMap<TreeNode, TreeNode> FindFather(TreeNode root) {
        // 定义最终返回的HashMap
        HashMap<TreeNode, TreeNode> ff = new HashMap<>();
        
        if (null == root) {
            return null;
        }
        if (null == root.left && null == root.right) {
            ff.put(root, root);
            return ff;
        }
        // 具体代码实现
        // 使用前序遍历的方式，找到每个节点与其父节点对应的关系
        // 定义一个stack
        Stack<TreeNode> st = new Stack<>();
        // 定义一个辅助节点
        TreeNode tn = root;
        // 初始化
        ff.put(root, root); // 根节点的父亲当然是他自己啦
        st.push(tn); // 将根节点压栈
        while (!st.isEmpty()) {
            tn = st.pop();
            if (null != tn.right) {
                st.push(tn.right);
                ff.put(tn.right, tn);
            }
            if (null != tn.left) {
                st.push(tn.left);
                ff.put(tn.left, tn);
            }
        }
        // 循环结束，我们得到了每个节点与其父节点对应的关系
        // 返回HashMap
        return ff;
    }
}