本文主要是介绍剑指 Offer 34. 二叉树中和为某一值的路径(回溯法),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
示例:
给定如下二叉树,以及目标和 sum = 22,5/ \4 8/ / \11 13 4/ \ / \7 2 5 1
返回:[[5,4,11,2],[5,8,4,5]
]
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
class Solution {//linklist到底是list还是queue还是stack?它是栈和队列LinkedList<Integer> path = new LinkedList<>();//栈List<List<Integer>> res=new LinkedList<>();public List<List<Integer>> pathSum(TreeNode root, int sum) {recur(root,sum);return res;}void recur(TreeNode root, int tar) {if (root==null){return;}path.add(root.val);//节点入栈tar=tar- root.val;if (tar==0&&root.left==null&&root.right==null){res.add(new LinkedList(path));}//如果当前节点不满足tar==0&&root.left==null&&root.right==null,怎么办呢?recur(root.left,tar);recur(root.right,tar);path.removeLast();//节点出栈。。。。。。}
}
这篇关于剑指 Offer 34. 二叉树中和为某一值的路径(回溯法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!