剑指offer代码解析——面试题25二叉树中和为某一值的路径

本题详细的分析过程均在代码注释中:

import java.util.Iterator;
import java.util.Stack;

/**
 * 题目:输入一棵二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。
 * PS:从根结点开始,一直到叶子结点形式一条路径。
 * @author 大闲人柴毛毛
 * @date 2016年3月15日
 */
public class PrintBinaryPath {
	/**
	 * 分析:要找出路径之和为指定整数的路径,就需要遍历二叉树的所有路径。
	 * 此外,由于路径是指根结点到叶子结点的线段,因此我们想到采用深度优先的方式遍历二叉树。
	 * 深度优先算法又分为:先序遍历、中序遍历、后序遍历,其中先序遍历符合我们的要求。
	 */
	
	/**
	 * 首先需要创建一个栈,用来保存当前路径的结点。
	 * 采用先序遍历算法遍历结点时,先将途中经过的结点均存入栈中,然后判断当前结点是否为叶子结点,若不是叶子结点的话,则递归遍历该结点的左孩子和右孩子;
	 * 若是叶子结点的话,计算下当前栈中所有结点之和是否为指定的整数,若是的话打印栈中所有元素。
	 * 然后这个函数在返回之前,将当前叶子结点从栈中删除。
	 */
	
	/**
	 * 打印二叉树中路径之和为n的路径
	 * @param root 二叉树
	 * @param n 路径之和
	 * @return 返回函数能否正确执行
	 */
	public static boolean printBinaryPath(BinaryTreeNode<Integer> root,int n){
		//树为空
		if(root==null){
			System.out.println("树为空!");
			return false;
		}
		
		//n小于0
		if(n<=0){
			System.out.println("n小于等于0!");
			return false;
		}
		
		//创建栈
		Stack<Integer> stack = new Stack<Integer>();
		//开始递归查找路径
		printBinaryPath(root,n,stack);
		
		return true;
	}

	
	
	/**
	 * 递归寻找路径之和为n的路径
	 * @param root 二叉树根结点
	 * @param n 指定整数
	 * @param stack 用于保存当前路径的栈
	 */
	private static void printBinaryPath(BinaryTreeNode<Integer> root, int n, Stack<Integer> stack) {
		//若当前根结点为叶子结点
		if(root.left==null && root.right==null){
			//将叶子结点入栈
			stack.add(root.data);
			
			//计算当前路径之和
			int sum = 0;
			Iterator<Integer> it = stack.iterator();
			while(it.hasNext())
				sum += it.next();
			
			//若当前路径之和==n,则打印这条路径
			if(sum==n){
				Iterator<Integer> it2 = stack.iterator();
				while(it2.hasNext())
					System.out.print(it2.next()+",");
				System.out.println("\n-------------------");
			}
			
			//将当前叶子结点出栈
			stack.pop();
			
			//返回上层结点
			return;
		}
		
		//若当前结点为非叶子结点
		else{
			//将根结点入栈
			stack.add(root.data);
			
			//若左孩子存在,递归左孩子
			if(root.left!=null)
				printBinaryPath(root.left,n,stack);
			
			//若右孩子存在,递归右孩子
			if(root.right!=null)
				printBinaryPath(root.right,n,stack);
			
			//将当前叶子结点出栈
			stack.pop();
			
			//返回上层结点
			return;
		}
	}
	
	
	
	/**
	 * 测试
	 */
	public static void main(String[] args){
		//构建二叉树
		BinaryTreeNode<Integer> node1 = new BinaryTreeNode<Integer>();
		BinaryTreeNode<Integer> node2 = new BinaryTreeNode<Integer>();
		BinaryTreeNode<Integer> node3 = new BinaryTreeNode<Integer>();
		BinaryTreeNode<Integer> node4 = new BinaryTreeNode<Integer>();
		BinaryTreeNode<Integer> node5 = new BinaryTreeNode<Integer>();
		
		node1.data = 10;
		node2.data = 5;
		node3.data = 12;
		node4.data = 4;
		node5.data = 7;
		
		node1.left = node2;
		node1.right = node3;

		node2.left = node4;
		node2.right = node5;
		
		printBinaryPath(node1,19);
	}
}




/**
 * 二叉树的结点
 */
class BinaryTreeNode<T>{
	T data;//结点的数据域
	BinaryTreeNode<T> left;//左子树
	BinaryTreeNode<T> right;//右子树
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程理解

数据结构(二):二叉搜索树(Binary Search Tree)

二分法的查找过程是,在一个有序的序列中,每次都会选择有效范围中间位置的元素作判断,即每次判断后,都可以排除近一半的元素,直到查找到目标元素或返回不存在,所以

801
来自专栏wym

树状数组理论基础

  树状数组(binary indexed trees,二进制索引树),最早由Peter M. Fenwick于1994年以“A New Data Struct...

572
来自专栏zaking's

用js来实现那些数据结构13(树01-二叉搜索树的实现)

  前一篇文章我们学会了第一个非顺序数据结构hashMap,那么这一篇我们来学学树,包括树的概念和一些相关的术语以及二叉搜索树的实现。唉?为什么不是树的实现,不...

37110
来自专栏和蔼的张星的图像处理专栏

算法1.排序二分查找及其变种

这个我也不知道能写多少,只是最近快放假了实在懒得看DSP了,而且卡在一个地方了,什么都不干又感觉心慌的很,所以又回头看看算法的东西。一些测试程序放在这里

782
来自专栏Vamei实验室

纸上谈兵: 树, 二叉树, 二叉搜索树

树的特征和定义 树(Tree)是元素的集合。我们先以比较直观的方式介绍树。下面的数据结构是一个树: ? 树有多个节点(node),用以储存元素。某些节点之间存在...

1937
来自专栏null的专栏

剑指Offer——编程题的Java实现

声明:我写这个的意图是我在看书的过程中,就我掌握的内容做一个笔记,没有抄袭的意图。再次说明一下,我找工作的过程中并不顺利,没有像那些牛人们拿到一大把的Offer...

5523
来自专栏数据结构与算法

P1305 新二叉树

题目描述 输入一串完全二叉树,用遍历前序打出。 输入输出格式 输入格式: 第一行为二叉树的节点数n。 后面n行,每一个字母为节点,后两个字母分别为其左右...

3368
来自专栏weixuqin 的专栏

数据结构学习笔记(树、二叉树)

2453
来自专栏Felix的技术分享

霍夫曼压缩算法

1988
来自专栏xcywt

《大话数据结构》树以及赫夫曼编码的例子

第六章 树 6.2 树的定义 树(Tree)的n个结点的有限集。当n=0时,称为空树。 任意一个非空树中: 1)有且仅有一个特定的称为根(root)的结点 2)...

3716

扫码关注云+社区