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.

节点可能为负数,寻找一条最路径使得所经过节点和最大。路径可以开始和结束于任何节点但是不能走回头路。

这道题虽然看起来不同寻常,但是想一下,可以发现不外乎二叉树的遍历+简单的动态规划思想。

我们可以把问题拆分开:即便最后的最大路径没有经过根节点,它必然也有自己的“最高点”,因此我们只要针对所有结点,求出:如果路径把这个节点作为“最高点”,路径最长可达多少?记为max。然后在max中求出最大值MAX即为所求结果。和“求整数序列中的最大连续子序列”一样思路。

下面就是找各个“最高点”对应的max之间的关系了。

我们拿根节点为例,对于经过根节点的最大路径的计算方式为:

我们找出左子树中以左孩子为起点的最大路径长度a,和右子树中以右孩子为起点的最大路径长度b。然后这个点的max=MAX(a+b+node.val,a+node.val,b+node.val,node.val)

因此我们定义一个函数来算上面的a或者b,它的参数是一个节点,它的返回值是最大路径长度,但是这个路径的起点必须是输入节点,而且路径必须在以起点为根节点的子树上。

那么函数func(node)的return值可以这样定义:returnMAX(func(node.left)+node.val,func(node.right)+node.val,node.val)

终止条件是node==null,直接返回0。

接着我们发现上述计算max和求出MAX的过程完全可以放到func(node)里去。

按照这个思路的代码,maxPathSumCore就是上面func(node)的实现:

/**
 * Definition for binary tree
 * struct TreeNode {
 *   int val;
 *   TreeNode *left;
 *   TreeNode *right;
 *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
	public:
	  int maxPathSum(TreeNode *root) {
		maxPathSumCore(root);
		return MAX;
	}
	int maxPathSumCore(TreeNode *node) {
		if(NULL == node) return 0;
		int a = maxPathSumCore(node -> left);
		int b = maxPathSumCore(node -> right);
		if((a+b+node->val) > MAX) MAX = (a+b+node->val);
		if((a+node->val) > MAX) MAX = (a+node->val);
		if((b+node->val) > MAX) MAX = (b+node->val);
		if(node->val > MAX) MAX = node->val;
		int maxViaThisNode = ((a + node->val) > node->val ? (a + node->val) : node->val);
		return (maxViaThisNode > (b + node->val) ? maxViaThisNode : (b + node->val));
	}
	private:
	  int MAX= -99999999;
}
;

时间复杂度 O(n),n为总节点数。

总结

以上就是本文关于java编程求二叉树最大路径问题代码分析的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!

时间: 2017-12-11

Java实现表达式二叉树

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

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

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

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编程求二叉树的镜像两种方法介绍

给出一棵二叉树,求它的镜像,如下图:右边是二叉树是左边二叉树的镜像. 仔细分析这两棵树的特点,看看能不能总结出求镜像的步骤.这两棵树的根节点相同,但他们的左右两个子节点交换了位置.因此我们不妨先在树中交换根节点的两个子节点,就得到了下面一幅图中的第二颗树 解法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 实现二叉树(链式存储结构)

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

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  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实现二叉树的创建及5种遍历方法(总结)

用java实现的数组创建二叉树以及递归先序遍历,递归中序遍历,递归后序遍历,非递归前序遍历,非递归中序遍历,非递归后序遍历,深度优先遍历,广度优先遍历8种遍历方式: package myTest; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Stack; public class myClass { public static void main(

java中关于Map的三种遍历方法详解

map的三种遍历方法!集合的一个很重要的操作---遍历,学习了三种遍历方法,三种方法各有优缺点~~ 复制代码 代码如下: /* * To change this template, choose Tools | Templates * and open the template in the editor. */package cn.tsp2c.liubao;import java.util.Collection;import java.util.HashMap;import java.util

Java中四种遍历List的方法总结(推荐)

实例如下: package com.ietree.basic.collection.loop; import java.util.ArrayList; import java.util.Iterator; import java.util.List; /** * List遍历 * * @author Dylan */ public class ListLoop { public static void main(String[] args) { // 初始化一个长度为10的ArrayList L

Map集合的四种遍历方式代码示例

很久以前写的代码,和上一个做比较吧!便于以后查看. import java.util.HashMap; import java.util.Iterator; import java.util.Map; public class TestMap { public static void main(String[] args) { Map<Integer, String> map = new HashMap<Integer, String>(); map.put(1, "a&

java读取XML文件的四种方法总结(必看篇)

JAVA操作XML文档主要有四种方式,分别是DOM.SAX.JDOM和DOM4J,DOM和SAX是官方提供的,而JDOM和DOM4J则是引用第三方库的,其中用的最多的是DOM4J方式.运行效率和内存使用方面最优的是SAX,但是由于SAX是基于事件的方式,所以SAX无法在编写XML的过程中对已编写内容进行修改,但对于不用进行频繁修改的需求,还是应该选择使用SAX. 下面基于这四种方式来读取XML文件. 第一,以DOM的方式实现. package xmls; import org.w3c.dom.D

java获取当前时间的四种方法代码实例

这篇文章主要介绍了java获取当前时间的四种方法代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 第一种:Date类 public class DateDemo { public static void main(String[] args) { Date day = new Date(); SimpleDateFormat dft = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); S

php解析xml 的四种简单方法(附实例)

XML处理是开发过程中经常遇到的,PHP对其也有很丰富的支持,本文只是对其中某几种解析技术做简要说明,包括:Xml parser, SimpleXML, XMLReader, DOMDocument. 1. XML Expat Parser: XML Parser使用Expat XML解析器.Expat是一种基于事件的解析器,它把XML文档视为一系列事件.当某个事件发生时,它调用一个指定的函数处理它.Expat是无验证的解析器,忽略任何链接到文档的DTD.但是,如果文档的形式不好,则会以一个错误

Map获取键值,Map的几种遍历方法总结(推荐)

Map获取键值 Map以按键/数值对的形式存储数据,和数组非常相似,在数组中存在的索引,它们本身也是对象. Map的接口 Map---实现Map Map.Entry--Map的内部类,描述Map中的按键/数值对. SortedMap---扩展Map,使按键保持升序排列 关于怎么使用,一般是选择Map的子类,而不直接用Map类. 下面以HashMap为例 public static void main(String args[]) { HashMap hashmap =new HashMap();