首页 > 代码库 > 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 二叉数 深度遍历,保存路径
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。