淘先锋技术网

首页 1 2 3 4 5 6 7

描述:

给定一个二叉树,找出所有路径中各节点相加总和等于给定 目标值 的路径。

一个有效的路径,指的是从根节点到叶节点的路径。

样例:

给定一个二叉树,和 目标值 = 5:

     1
    / \
   2   4
  / \
 2   3

返回:

[
  [1, 2, 2],
  [1, 4]
]

Java代码:

二叉树:先序遍历(根左子树右子树),中序遍历(左子树根右子树),后序遍历(左子树右子树根),层次遍历(第一层第二层。。。)
图:深度优先遍历(类似二叉树先序),广度优先遍历(类似二叉树层次遍历)
递归:
非递归:
深度-》栈
广度-》队列

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root the root of binary tree
     * @param target an integer
     * @return all valid paths
     */
    public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
		 
		 List<List<Integer>> roads = new ArrayList<List<Integer>>();
		 Stack <Integer> road = new Stack<Integer>();
		 int sum = 0;
		 
		 if(root == null){
			 return roads;
		 }
		 
		 dpTree(roads,road,root,sum,target);
		 
		 return roads;
	 }
	 
	 public void dpTree(List<List<Integer>> roads,Stack <Integer> road,TreeNode root,int sum,int target){
		 if(root == null){
			 return;
		 }
		 
		 if(root != null){
			 road.push(root.val);
			 sum = sum + root.val;
		 }
		 
		 if(root.left == null && root.right == null){
			 
			 if(sum == target){
				 List <Integer> targetRoad = new ArrayList<Integer>(road);
				 roads.add(targetRoad);
			 }

			 sum = sum - root.val;
			 road.pop();
			 return;
		 }
		 
		 dpTree(roads,road,root.left,sum,target);
		 dpTree(roads,road,root.right,sum,target);
		 road.pop();
		 sum = sum - root.val;
	 }
}