剑指offer（第二版）面试题34：二叉树中和为某一值的路径（Java）

Bertha 。 2021-11-11 08:06 162阅读 0赞

### 题目 ###

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。二叉树结点的定义如下：

struct BinaryTreeNode{
    	int m_nValue;
    	BinaryTreeNode* m_pLeft;
    	BinaryTreeNode* m_pRight;
    }

### **解题思路** ###

先说一个具体的例子，输入下图的二叉树和整数22，则打印出两条路径，第一条路径包含结点10、12，第二条路径包含结点10、5和7。

![2018060814201646][]

![20180608143045286][]

上面的图具体的分析了这个示例。当用前序遍历的方式访问到某一结点时，我们把该结点添加到路径上，并累加该结点的值。如果该结点为叶结点并且路径中结点值的和刚好等于输入的整数，则当前的路径符合要求，我们把它打印出来。如果当前结点不是叶结点，则继续访问它的子结点。当前结点访问结束后，递归函数将自动回到它的父结点。因此我们在函数退出之前要在路径上删除当前结点并减去当前结点的值，以确保返回父结点时路径刚好是从根节点到父结点的路径。从分析中得知我们需要借助栈来保存路径的数据。

代码如下：

import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    
    public class test {
    
    	
    	public static void main(String[] args) {
    		BNode node1 = new BNode(10);
    		BNode node2 = new BNode(5);
    		BNode node3 = new BNode(12);
    		BNode node4 = new BNode(4);
    		BNode node5 = new BNode(7);
    		node1.left=node2;
    		node1.right=node3;
    		node2.left=node4;
    		node2.right=node5;
    		
    		System.out.print(find(node1,22));
    	}
    
    	public static ArrayList<ArrayList<Integer>> find(BNode n,int target) {
    		if(n==null) {
    			return null;
    		}
    		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    		Stack<Integer> stack = new Stack<Integer>();
    		path(n,target,res,stack);
    		return res;
    	}
    	
    	public static void path(BNode n,int target,ArrayList<ArrayList<Integer>> res,Stack<Integer> stack) {
    		
    		if(n==null)
    			return;
    		if(n.left==null&&n.right==null) {
    			if(target==n.data) {
    				ArrayList<Integer> list = new ArrayList<Integer>();
    				for(int i:stack) {
    					list.add(i);
    				}
    				list.add(n.data);
    				res.add(list);
    			}
    		}else {
    			stack.push(n.data);
    			path(n.left,target-n.data,res,stack);
    			path(n.right,target-n.data,res,stack);
    			stack.pop();
    		}
    	}
    	
    	public static class BNode{
    		public BNode left;
    		public BNode right;
    		public int data;
    		
    		BNode(int data){
    			this.left = null;
    			this.right = null;
    			this.data = data;
    		}
    		
    		public String toString() {
    			return "BNode [data=" + data + ", left=" + left + ", right=" + right
    					+ "]";
    		}
     
    	}
    	
    }

[2018060814201646]: /images/20211109/3df6cff98502404ca83a65a10b2f6068.png
[20180608143045286]: /images/20211109/0ed022da2be34c0e93398e29db1bebd1.png