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编程求二叉树最大路径问题代码分析的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！

赞 (0)

相关推荐

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

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

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

  • 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进行红黑二叉树遍历的方法

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

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

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

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

  • Java实现表达式二叉树

    Java实现表达式二叉树

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

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

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

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

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

  • 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实现打印二叉树所有路径的方法.分享给大家供大家参考,具体如下: 问题: 给一个二叉树,把所有的路径都打印出来. 比如,对于下面这个二叉树,它所有的路径为: 8 -> 3 -> 1 8 -> 2 -> 6 -> 4 8 -> 3 -> 6 -> 7 8 -> 10 -> 14 -> 13 思路: 从根节点开始,把自己的值放在一个数组里,然后把这个数组传给它的子节点,子节点同样把自己的值放在这个数组里,又传给自己的子节点,

  • Java编程利用socket多线程访问服务器文件代码示例

    这篇文章将向大家展示Java编程利用socket多线程访问服务器文件代码示例,如果您想先了解Java多线程socket编程的基础知识,可以看下这篇文章:Java多线程编程实现socket通信示例代码. 接下来进入正文,我们看看利用socket多线程访问服务器代码: ServerMain.java package com.ysk.webServer; import java.io.File; import java.io.IOException; import java.net.ServerSoc

  • Java编程常见内存溢出异常与代码示例

    Java 堆是用来存储对象实例的, 因此如果我们不断地创建对象, 并且保证 GC Root 和创建的对象之间有可达路径以免对象被垃圾回收, 那么当创建的对象过多时, 会导致 heap 内存不足, 进而引发 OutOfMemoryError 异常. /** * @author xiongyongshun * VM Args: java -Xms10m -Xmx10m -XX:+HeapDumpOnOutOfMemoryError */ public class OutOfMemoryErrorTe

  • java编程进行动态编译加载代码分享

    简述 该类使用javax.tools.ToolProvider自带的JavaCompiler进行编译,使用IO的File及NIO的Files进行对应的路径创建.读取及拷贝,使用正则表达式进行包名与目录的转换,我只是将这些东西做了个容错整合,没什么技术含量,就为个方便吧. 模块API class DynamicReactor://空参构造 public Class<?> dynamicCompile(String srcPath);//输入一个指定的源文件路径,若编译.拷贝成功则返回该类对应的C

  • Java编程实现深度优先遍历与连通分量代码示例

    Java编程实现深度优先遍历与连通分量代码示例

    深度优先遍历 深度优先遍历类似于一个人走迷宫: 如图所示,从起点开始选择一条边走到下一个顶点,没到一个顶点便标记此顶点已到达. 当来到一个标记过的顶点时回退到上一个顶点,再选择一条没有到达过的顶点. 当回退到的路口已没有可走的通道时继续回退. 而连通分量,看概念:无向图G的极大连通子图称为G的连通分量( Connected Component).任何连通图的连通分量只有一个,即是其自身,非连通的无向图有多个连通分量. 下面看看具体实例: package com.dataStructure.gra

  • Java编程将汉字转Unicode码代码示例

    上一次接触到编码的知识,还是上大学的时候,那时候学的是通信工程专业,有关编码的内容,不记得是在通信原理还是信息论与编码里面学到的了.却依然记得那个信息论与编码的老师,最喜欢吃的是尖椒肥肠盖饭,不知道是尖椒肥肠吃多了还是太聪明的缘故,三十多岁就开始拜顶了.那四年真是一段难忘的回忆... 话不多说,咱们进入正题.这里是一个简单的Java编程将汉字转Unicode码代码示例,下面是代码: package me.socketthread; public class ToUnicode { /** * @

  • Java编程GUI中的事件绑定代码示例

    程序绑定的概念: 绑定指的是一个方法的调用与方法所在的类(方法主体)关联起来.对java来说,绑定分为静态绑定和动态绑定:或者叫做前期绑定和后期绑定 静态绑定: 在程序执行前方法已经被绑定,此时由编译器或其它连接程序实现.例如:C. 针对java简单的可以理解为程序编译期的绑定:这里特别说明一点,java当中的方法只有final,static,private和构造方法是前期绑定 动态绑定 后期绑定:在运行时根据具体对象的类型进行绑定. 若一种语言实现了后期绑定,同时必须提供一些机制,可在运行期间

  • java编程基础之模仿用户登录代码分享

    上一篇文章我们了解了Java背包问题求解实例代码,接下来我们看看Java中模仿用户登录的相关代码,下面是具体内容. 基于用户从控制台输入模拟的简陋用户登录验证Demo原理: 利用 Scanner 类中 nextLine() 提取用户从控制台输入的字符串信息 利用 String 类的 equals 方法进行用户输入验证 import java.util.Scanner; public class Login { public static void main(String[] args) { //

随机推荐