java中如何求二叉樹(shù)最大路徑

這篇文章給大家分享的是有關(guān)java中如何求二叉樹(shù)最大路徑的內(nèi)容。小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考，一起跟隨小編過(guò)來(lái)看看吧。

題目：

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.

節(jié)點(diǎn)可能為負(fù)數(shù)，尋找一條最路徑使得所經(jīng)過(guò)節(jié)點(diǎn)和最大。路徑可以開(kāi)始和結(jié)束于任何節(jié)點(diǎn)但是不能走回頭路。

這道題雖然看起來(lái)不同尋常，但是想一下，可以發(fā)現(xiàn)不外乎二叉樹(shù)的遍歷+簡(jiǎn)單的動(dòng)態(tài)規(guī)劃思想。

我們可以把問(wèn)題拆分開(kāi)：即便最后的最大路徑?jīng)]有經(jīng)過(guò)根節(jié)點(diǎn)，它必然也有自己的“最高點(diǎn)”，因此我們只要針對(duì)所有結(jié)點(diǎn)，求出：如果路徑把這個(gè)節(jié)點(diǎn)作為“最高點(diǎn)”，路徑最長(zhǎng)可達(dá)多少？記為max。然后在max中求出最大值MAX即為所求結(jié)果。和“求整數(shù)序列中的最大連續(xù)子序列”一樣思路。

下面就是找各個(gè)“最高點(diǎn)”對(duì)應(yīng)的max之間的關(guān)系了。

我們拿根節(jié)點(diǎn)為例，對(duì)于經(jīng)過(guò)根節(jié)點(diǎn)的最大路徑的計(jì)算方式為：

我們找出左子樹(shù)中以左孩子為起點(diǎn)的最大路徑長(zhǎng)度a，和右子樹(shù)中以右孩子為起點(diǎn)的最大路徑長(zhǎng)度b。然后這個(gè)點(diǎn)的max=MAX(a+b+node.val,a+node.val,b+node.val,node.val)

因此我們定義一個(gè)函數(shù)來(lái)算上面的a或者b，它的參數(shù)是一個(gè)節(jié)點(diǎn)，它的返回值是最大路徑長(zhǎng)度，但是這個(gè)路徑的起點(diǎn)必須是輸入節(jié)點(diǎn)，而且路徑必須在以起點(diǎn)為根節(jié)點(diǎn)的子樹(shù)上。

那么函數(shù)func(node)的return值可以這樣定義：returnMAX(func(node.left)+node.val,func(node.right)+node.val,node.val)

終止條件是node==null，直接返回0。

接著我們發(fā)現(xiàn)上述計(jì)算max和求出MAX的過(guò)程完全可以放到func(node)里去。

按照這個(gè)思路的代碼，maxPathSumCore就是上面func(node)的實(shí)現(xiàn)：

/**
 * 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;
}
;

時(shí)間復(fù)雜度 O(n)，n為總節(jié)點(diǎn)數(shù)。

感謝各位的閱讀！關(guān)于“java中如何求二叉樹(shù)最大路徑”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，讓大家可以學(xué)到更多知識(shí)，如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！