首页 > 代码库 > Path Sum 2 --java 二叉数 深度遍历,保存路径

Path Sum 2 --java 二叉数 深度遍历,保存路径

在Path SUm 1中(http://www.cnblogs.com/hitkb/p/4242822.html)

我们采用栈的形式保存路径,每当找到符合的叶子节点,就将栈内元素输出。注意存在多条路径的情况。

 public List<List<Integer>> pathSum(TreeNode root, int sum) {        List<List<Integer>>list=new ArrayList<>();        Stack<TreeNode> stack = new Stack<>();        int total = 0;        if (root == null)            return list;        TreeNode qNode=root;        while (root != null) {            while (root.left != null) {                stack.push(root);                total += root.val;                root = root.left;            }//左节点压栈            while (root != null && (root.right == null || root.right == qNode)) {//||前面是判断是否是叶子节点,后面是弹出右节点                                if(root.right==null&&root.left==null){                    if((total+root.val)==sum){//此处是探测当前访问加上最终的叶子节点,是否等于输入。                        list.add(getstack(stack,root.val));                    }                }                qNode = root;// 记录上一个已输出节点                if (stack.empty())                    return list;                root = stack.pop();                total-=root.val;            }            stack.push(root);            total+=root.val;            root = root.right;        }        return list;    }    /*统计栈内元素     *      *      */    public  List<Integer> getstack(Stack<TreeNode>stack,Integer a){        Stack<TreeNode>stack2=(Stack<TreeNode>) stack.clone();        List<Integer>list=new ArrayList<>();        list.add(a);        while(!stack2.isEmpty()){            TreeNode ouTreeNode=stack2.pop();            list.add(0, ouTreeNode.val);        }        return list;    }

 

Path Sum 2 --java 二叉数 深度遍历,保存路径