寻找二元树中和为某一值的所有路径（Java）

题目：输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。

例如输入整数22和如下二元树

                                            10
                                           /   \
                                          5     12
                                        /   \   
                                    　4     7 

则打印出两条路径：10, 12和10, 5, 7。

题目来源：http://zhedahht.blog.163.com/blog/static/254111742007228357325/

分析：题目需要从根节点开始遍历整棵树，并顺着路径记录节点的累加和，当到达某一节点时首先应该判别此路径上的节点和是都已经大于了需要的整数，如果大于，则放弃此条路径，如果小于则分别进入左、右节点继续上述步骤，当到达叶节点时判断累计值是否为指定整数，如相同则找到一条路径。为了打印出满足条件的路径，需要在遍历过程中记录节点顺序，本例采用Java中的LinkedList模拟先进先出队列的数据结构，将遍历过程中的节点依次加入队列，路径满足条件后从队列依次取出各节点值并打印。

代码如下：

package sumonepath;

/**
 * 二元树中和为某一值的所有路径
 * @author DHC
 *
 */
public class SumOnePath {

	private final int resultData = 22;
	
	private static Node tree = SumOnePath.getTree();
	
	public static void main(String[] args) {
		new SumOnePath().doJob(tree);
	}
	
	private void doJob(Node tree) {
		
		// 将本节点值加入路径队列
		tree.getDataList().add(tree.getData());
		
		// 更新路径节点的累加值
		tree.setSum(tree.getSum() + tree.getData());
		int sum = tree.getSum();
		
		if (sum > resultData) {
			return;
		}
		
		Node leftNode = tree.getLeftNode();
		Node rightNode = tree.getRightNode();
		
		if (leftNode != null || rightNode != null) {
			if (leftNode != null) {
				// 将路径加入左节点
				leftNode.getDataList().addAll(tree.getDataList());
				// 将累加值加入左节点
				leftNode.setSum(tree.getSum());
				doJob(leftNode);
			}
			
			if (rightNode != null) {
				rightNode.getDataList().addAll(tree.getDataList());
				rightNode.setSum(tree.getSum());
				doJob(rightNode);
			}
		} else {
			if (sum == resultData) {
				printTree(tree);
			}
		}
	}
	
	/**
	 * 从队列取数据并打印
	 * @param node
	 */
	private void printTree(Node node) {
		int size = node.getDataList().size();
		for (int i = 0; i < size; i++) {
			System.out.print(node.getDataList().pollFirst()+ "  ");
		}
		System.out.print("\n");
	}
	
	/**
	 * 获取树
	 * @return
	 */
	private static Node getTree() {
		Node node = new Node(10);
		Node node1 = new Node(5);
		Node node2 = new Node(4);
		Node node3 = new Node(7);
		Node node4 = new Node(12);
		
		node.setLeftNode(node1);
		node1.setLeftNode(node2);
		node.setRightNode(node4);
		node1.setRightNode(node3);
		
		return node;
	}
}

 

 

package sumonepath;

import java.util.LinkedList;

public class Node {
	
	private Node leftNode;
	
	private Node rightNode;
	
	private int data;
	
	/**
	 * 路径节点累加值
	 */
	private int sum;
	
	/**
	 * 路径记录队列
	 */
	private LinkedList<Integer> dataList = new LinkedList<Integer>();
	
	public LinkedList<Integer> getDataList() {
		return dataList;
	}

	public void setDataList(LinkedList<Integer> dataList) {
		this.dataList = dataList;
	}

	public int getSum() {
		return sum;
	}

	public void setSum(int sum) {
		this.sum = sum;
	}

	public Node(int data) {
		this.data = data;
	}

	public Node getLeftNode() {
		return leftNode;
	}

	public Node getRightNode() {
		return rightNode;
	}

	public void setLeftNode(Node leftNode) {
		this.leftNode = leftNode;
	}

	public void setRightNode(Node rightNode) {
		this.rightNode = rightNode;
	}

	public int getData() {
		return data;
	}

	public void setData(int data) {
		this.data = data;
	}

}