Java二叉树路径和代码示例

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

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

样例

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

  1
 / \
 2 4
 / \
 2 3

返回：

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

代码如下：

/**
 * 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) {
		// Write your code here
		return dfs(root,new ArrayList<Integer>(),0,new ArrayList<List<Integer>>(),target);
	}
	public List<List<Integer>> dfs(TreeNode root,List<Integer> node, int sum, List<List<Integer>> paths,int target)
	 {
		if(root==null)
		  {
			return new ArrayList<List<Integer>>();
		}
		List<List<Integer>> path=new ArrayList<List<Integer>>();
		if(root.left!=null)
		  {
			List<Integer> nodes=new ArrayList<Integer>();
			if(node!=null)
			  {
				nodes.addAll(node);
			}
			nodes.add(root.val);
			List<List<Integer>> temp=dfs(root.left,nodes,sum+root.val,paths,target);
			if(temp!=null)
			   {
				path.addAll(temp);
			}
		}
		if(root.right!=null)
		  {
			List<Integer> nodes=new ArrayList<Integer>();
			if(node!=null)
			  {
				nodes.addAll(node);
			}
			nodes.add(root.val);
			List<List<Integer>> temp=dfs(root.right,nodes,sum+root.val,paths,target);
			if(temp!=null)
			   {
				path.addAll(temp);
			}
		}
		if(root.left==null&&root.right==null)
		  {
			List<Integer> nodes=new ArrayList<Integer>();
			if(node!=null)
			  {
				nodes.addAll(node);
			}
			nodes.add(root.val);
			if(sum+root.val==target)
			   {
				path.add(nodes);
			} else{
				path=new ArrayList<List<Integer>>();
			}
		}
		return path;
	}
}

referance

java编程求二叉树最大路径问题代码分析

java中继承测试代码分析

总结

以上就是本文关于Java二叉树路径和代码示例的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！

赞 (0)

相关推荐

  • java编程求二叉树最大路径问题代码分析

    题目: Binary Tree Maximum Path Sum Given a binary tree, find the maximum path sum. The path may start and end at any node in the tree. For example: Given the below binary tree, 1 / \ 2 3 Return 6. 节点可能为负数,寻找一条最路径使得所经过节点和最大.路径可以开始和结束于任何节点但是不能走回头路. 这道题虽然

  • Java实现表达式二叉树

    Java实现表达式二叉树

    什么是二叉树,这里不再介绍,可以自行百度:二叉树.在这里利用java实现"表达式二叉树". 表达式二叉树的定义  第一步先要搞懂表达式二叉树是个什么东东?举个栗子,表达式:(a+b×(c-d))-e/f.将数字放在叶子节点,将操作符放在分支节点,就构成了一个二叉树,由于存储的是一个表达式,称之为"表达式二叉树". 童靴们可能好奇这个到底是怎么构建的?就拿45+23*56/2-5来说吧.首先取出第一个数字45放在叶子节点,遇到"+"后将其放到分支节

  • JAVA 实现二叉树（链式存储结构）

    JAVA 实现二叉树（链式存储结构）

    二叉树的分类(按存储结构) 树的分类(按存储结构) 顺序存储(用数组表示(静态二叉树))   链式存储 一些特别的二叉根: 完全二叉树,平衡二叉树(AVL),线索二叉树,三叉的(带父亲的指针)    二叉搜索树或者叫二叉 查找树(BST)  所用二叉树如下图所示: 二叉树的Java实现(链式存储结构) class TreeNode { private int key = 0; private String data = null; private boolean isVisted = false

  • 图解红黑树及Java进行红黑二叉树遍历的方法

    图解红黑树及Java进行红黑二叉树遍历的方法

    红黑树 红黑树是一种数据结构与算法课堂上常常提到但又不会细讲的树,也是技术面试中经常被问到的树,然而无论是书上还是网上的资料,通常都比较刻板难以理解,能不能一种比较直观的方式来理解红黑树呢?本文将以图形的方式来解释红黑树的插入与删除操作. 对树结构的学习是一个递进的过程,我们通常所接触的树都是二叉树,二叉树简单来说就是每个非叶子节点都有且只有两个孩子,分别叫做左孩子和右孩子.二叉树中有一类特殊的树叫二叉查找树,二叉查找树是一种有序的树,对于每个非叶子节点,其左子树的值都小于它,其右子树的值都大于

  • Java编程求二叉树的镜像两种方法介绍

    Java编程求二叉树的镜像两种方法介绍

    给出一棵二叉树,求它的镜像,如下图:右边是二叉树是左边二叉树的镜像. 仔细分析这两棵树的特点,看看能不能总结出求镜像的步骤.这两棵树的根节点相同,但他们的左右两个子节点交换了位置.因此我们不妨先在树中交换根节点的两个子节点,就得到了下面一幅图中的第二颗树 解法1(递归) 思路1:如果当前节点为空,返回,否则交换该节点的左右节点,递归的对其左右节点进行交换处理. /*class TreeNode{ int val; TreeNode left=null; TreeNode right=null;

  • java 实现最小二叉树堆排序的实例

    java 实现最小二叉堆排序的实例 写在前面: 一觉醒来,我就突然有灵感了...... 最小二叉堆定义: 二叉堆是完全二元树或者是近似完全二元树,最小二叉堆是父结点的键值总是小于或等于任何一个子节点的键值的堆堆. 存储: 二叉堆一般用数组来表示. 根节点在数组中的位置是0,第n个位置的子节点分别在2n+1和 2n+2: 位置k的叶子的父节点位置为(k-1)/2: 实现: /** * @description 元素添加到末尾,和它的父节点比,如果比它小就交换 * @param array * *

  • Java完全二叉树的创建与四种遍历方法分析

    Java完全二叉树的创建与四种遍历方法分析

    本文实例讲述了Java完全二叉树的创建与四种遍历方法.分享给大家供大家参考,具体如下: 有如下的一颗完全二叉树: 先序遍历结果应该为:1  2  4  5  3  6  7 中序遍历结果应该为:4  2  5  1  6  3  7 后序遍历结果应该为:4  5  2  6  7  3  1 层序遍历结果应该为:1  2  3  4  5  6  7 二叉树的先序遍历.中序遍历.后序遍历其实都是一样的,都是执行递归操作. 我这记录一下层次遍历吧:层次遍历需要用到队列,先入队在出队,每次出队的元素

  • Java语言描述二叉树的深度和宽度

    解释: 二叉树的深度:从根结点到叶结点依次经过的结点(含根.叶结点)形成树的一条路径,最长路径的长度为树的深度. 二叉树的宽度:二叉树的每一层中都有一定数量的节点,节点数最多的那一层的节点数叫做二叉树的宽度. 思路:递归实现. 1.每个节点都可以看作根节点 2.根节点(任意一个节点)的深度等于它的左子树或右子树深度最大值+1 3.从根结点开始遍历,若遍历到叶子节点,深度为0 //二叉树的深度 public static int Depth(node root){ if(root == null)

  • Java二叉树路径和代码示例

    给定一个二叉树,找出所有路径中各节点相加总和等于给定 目标值 的路径. 一个有效的路径,指的是从根节点到叶节点的路径. 样例 给定一个二叉树,和 目标值 = 5: 1 / \ 2 4 / \ 2 3 返回: [ [1, 2, 2], [1, 4] ] 代码如下: /** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public Tree

  • Java算法之堆排序代码示例

    Java算法之堆排序代码示例

    堆是一种特殊的完全二叉树,其特点是所有父节点都比子节点要小,或者所有父节点都比字节点要大.前一种称为最小堆,后一种称为最大堆. 比如下面这两个: 那么这个特性有什么作用?既然题目是堆排序,那么肯定能用来排序.想要用堆排序首先要创建一个堆,如果对4 3 6 2 7 1 5这七个数字做从小到大排序,需要用这七个数创建一个最大堆,来看代码: public class HeapSort { private int[] numbers; private int length; public HeapSor

  • java自定义类加载器代码示例

    如果要使用自定义类加载器加载class文件,就需要继承java.lang.ClassLoader类. ClassLoader有几个重要的方法: protectedClassLoader(ClassLoaderparent):使用指定的.用于委托操作的父类加载器创建新的类加载器. protectedfinalClass<?>defineClass(Stringname,byte[]b,intoff,intlen):将一个byte数组转换为Class类的实例. protectedClass<

  • Java动态编译执行代码示例

    在某些情况下,我们需要动态生成java代码,通过动态编译,然后执行代码.JAVAAPI提供了相应的工具(JavaCompiler)来实现动态编译.下面我们通过一个简单的例子介绍,如何通过JavaCompiler实现java代码动态编译. 一.获取JavaCompiler JavaCompiler compiler = ToolProvider.getSystemJavaCompiler(); 获取JDK提供的java编译器,如果没有提供编译器,则返回null: 二.编译 //获取java文件管理

  • java语言中封装类代码示例

    在面向对象程序设计方法中,封装(Encapsulation)是指一种将抽象性函式接口的实现细节部分包装'隐藏起来的方法.数据被保护在内部,隐藏内部实现细节,对外提供接口与外部交互. 使用封装的步骤 将类的所有属性使用关键字private去修饰,把它们变成私有的,不允许外部类直接访问 生成或者提供公共的setter/getter方法去操作这些被隐藏起来的属性 在类自己的 setter/getter方法中加入逻辑控制,以确保数据访问的有效性和安全性实例 让我们来看一个java封装类的例子: /* 文

  • Java读写ini文件代码示例

    本文实例主要实现Java读写ini文件,具体如下,代码中有详细注释. 在java中,配置文件一般主要是两种形式:xml文件或者property文件.但大部分人都习惯使用ini文件,而且ini文件的分节以及注释功能,比起xml,也是易懂易用的. 实例代码: package com.epoint.tools; import java.io.FileInputStream; import java.io.FileOutputStream; import java.io.OutputStream; im

  • java tostring方法重写代码示例

    当需要将一个对象输出到显示器时,通常要调用他的toString()方法,将对象的内容转换为字符串.java中的所有类默认都有一个toString()方法 默认情况下 System.out.println(对象名)或者System.out.println(对象名.toString())输出的是此对象的类名和此对象对应内存的首地址 如果想自定义输出信息必须重写toString()方法 注意事项 1.必须被声明为public 2.返回类型为String 3.方法的名称必须为toString,且无参数

  • Java中Switch用法代码示例

    一.java当中的switch与C#相比有以下区别 注:在java中switch后的表达式的类型只能为以下几种:byte.short.char.int(在Java1.6中是这样),  在java1.7后支持了对string的判断 还有一点要注意的是:在java中如果switch的case语句中少写了break;这个关键字,在编译的时候并没有报错.但是在执行的时候会一直执行所有case条件下的语句并不是去判断,所以会一直执行直到遇到break关键字跳出或者一直执行到defaut语句. 还有就是如果

  • Java编程异常简单代码示例

    Java编程异常简单代码示例

    练习1 写一个方法void triangle(int a,int b,int c),判断三个参数是否能构成一个三角形.如果不能则抛出异常IllegalArgumentException,显示异常信息:a,b,c "不能构成三角形":如果可以构成则显示三角形三个边长.在主方法中得到命令行输入的三个整数,调用此方法,并捕获异常. 两边之和大于第三边:a+b>c 两边之差小于第三边:c-a package 异常; import java.util.Arrays; import java

  • java编程队列数据结构代码示例

    java编程队列数据结构代码示例

    队列是一种特殊的线性表,只允许在表的前端进行删除,在表的后端进行插入,表的前端称为(front)队头,表的后端称为(rear)队尾. 所以队列跟生活的场景很是相似,在电影院买电影票,人们排成一排,第一个人进入队尾最先到达队头后买票进入影院,后面排队的人按照排队的次序买到票后进入影院. 所以 队列是一种先进先出的数据结构(FIFO). 编程实现对循环链队列的入队和出队操作. ⑴根据输入的队列长度n和各元素值建立一个带头结点的循环链表表示的队列(循环链队列),并且只设一个尾指针来指向尾结点,然后输出

随机推荐