leetcode124：二叉树中的最大路径和

题目链接

leetcode

题目描述

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。

C++ 代码

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
using namespace std;

// 二叉树结点的定义
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

const int NULL_NODE = -1001;

// 辅助函数：创建二叉树
TreeNode* createTree(const vector<int>& nums) {
    if (nums.empty()) return nullptr;

    TreeNode* root = new TreeNode(nums[0]);
    queue<TreeNode*> queue;
    queue.push(root);
    int i = 1;
    while (!queue.empty() && i < nums.size()) {
        TreeNode* node = queue.front(); queue.pop();
        if (nums[i] != NULL_NODE) {
            node->left = new TreeNode(nums[i]);
            queue.push(node->left);
        }
        i ++;
        if (i < nums.size() && nums[i] != NULL_NODE) {
            node->right = new TreeNode(nums[i]);
            queue.push(node->right);
        }
        i ++;
    }

    return root;
}

// 辅助函数：层序遍历打印二叉树
void levelOrderTraversal(TreeNode* root) {
    if (root == nullptr) return;

    queue<TreeNode*> queue;
    queue.push(root);
    while (!queue.empty()) {
        TreeNode* node = queue.front(); queue.pop();
        cout << node->val << " ";
        if (node->left != nullptr) queue.push(node->left);
        if (node->right != nullptr) queue.push(node->right);
    }
    cout << endl;
}

// 辅助函数：释放二叉树
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

/*
    递归实现
    
    树中每条路径，都存在一个离根结点最近的点，把它记为割点，用割点可以将整条路径分为两部分。
    从该结点向左子树延伸的路径，从该结点向右子树延伸的部分，两部分都是自上而下延伸。
    树的遍历（后序遍历）
    递归遍历整棵树，递归时维护从每个结点开始向下延伸的最大路径和。
    对于每个点，递归计算完左右子树后，得到以这个点为割点的最大路径。
    然后维护从这个点向下延伸的最大路径，从左右子树的路径中选择权值大的一条延伸。

    时间复杂度：O(n)
        其中 n 是二叉树中的结点个数。
        每个结点仅会遍历一次，所以时间复杂度是 O(n)。
    空间复杂度：O(n)
        主要取决于递归调用层数，最大层数等于二叉树的高度。
        最坏情况下，二叉树的高度等于二叉树中的结点个数。
*/
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return res;
    }

    int dfs(TreeNode* node) {
        if (node == nullptr) return 0;
        
        // 递归计算左右子树的最大路径和
        int left = max(0, dfs(node->left));
        int right = max(0, dfs(node->right));
        // 更新答案
        res = max(res, node->val + left + right);

        // 返回该结点的最大路径和
        return node->val + max(left, right);
    }

private:
    int res = INT_MIN;
};

/*
    迭代实现，思路同上
*/
class Solution_1 {
public:
    int maxPathSum(TreeNode* root) {
        // 使用 unordered_map 存储结点及其最大路径和
        unordered_map<TreeNode*, int> map;
        map[nullptr] = 0;
        // 使用栈存储结点
        stack<TreeNode*> stk;
        stk.push(root);

        int res = INT_MIN;
        while (!stk.empty()) {
            TreeNode* node = stk.top(); // 获取栈顶结点
            
            // 若左子结点和右子结点都已计算，则处理当前结点
            if ((map.find(node->left) != map.end()) && (map.find(node->right) != map.end())) {
                int a = node->val;
                int b = node->val + map[node->left];
                int c = node->val + map[node->right];
                int nodeVal = max(a, max(b, c)); // 当前结点及其子结点所能构成的最大路径和
                map[node] = nodeVal;

                int d = node->val + map[node->left] + map[node->right]; // 以当前结点为起点，包含左右子结点的最大路径和
                res = max(res, max(nodeVal, d));
                stk.pop();
            } else {
                if (node->left && map.find(node->left) == map.end()) {
                    stk.push(node->left);
                }
                if (node->right && map.find(node->right) == map.end()) {
                    stk.push(node->right);
                }
            }
        }

        return res;
    }
};

int main() {
    // 示例输入
    Solution solution;
    vector<int> nums = {-10,9,20,NULL_NODE,NULL_NODE,15,7};

    // 创建二叉树
    TreeNode* root = createTree(nums);
    levelOrderTraversal(root);

    // 计算最大路径和
    int result = solution.maxPathSum(root);
    // 打印结果
    cout << "Max Path Sum: " << result << endl;

    // 释放内存
    deleteTree(root);

    return 0;
}

Golang 代码

package main

import (
	"fmt"
	"math"
)

// TreeNode 定义二叉树节点
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// createTree 根据层序遍历的值创建二叉树
func createTree(values []int) *TreeNode {
	if len(values) == 0 || values[0] == -1 {
		return nil
	}

	root := &TreeNode{Val: values[0]}
	queue := []*TreeNode{root}
	i := 1

	for i < len(values) {
		node := queue[0]
		queue = queue[1:]

		// 左子节点
		if i < len(values) && values[i] != -1 {
			node.Left = &TreeNode{Val: values[i]}
			queue = append(queue, node.Left)
		}
		i++

		// 右子节点
		if i < len(values) && values[i] != -1 {
			node.Right = &TreeNode{Val: values[i]}
			queue = append(queue, node.Right)
		}
		i++
	}

	return root
}

/*
    基本思路：
        深度优先搜索 (DFS)：
            使用 DFS 遍历二叉树，计算每个节点的最大路径和。
            对于每个节点，计算其左子树和右子树的最大路径和，并更新全局最大路径和。
        路径和的计算：
            对于每个节点，计算经过该节点的路径和：node.Val + left + right，
            其中 left 和 right 是左子树和右子树的最大路径和。
            更新全局最大路径和。
        返回值：
            返回当前节点的最大路径和，供其父节点使用：node.Val + max(left, right)。

    时间复杂度：O(n)
        其中 n 是二叉树中节点的数量。
        每个节点访问一次，因此时间复杂度为 O(n)。
    空间复杂度：O(n)
        递归调用栈的深度取决于树的高度，
        最坏情况下（树完全不平衡）为 O(n)，最好情况下（树完全平衡）为 O(logn)。
        因此，空间复杂度为 O(n)。
*/
// maxPathSum 计算二叉树中的最大路径和
func maxPathSum(root *TreeNode) int {
    maxSum := math.MinInt64 // 初始化为最小整数

	var dfs func(node *TreeNode) int
	dfs = func(node *TreeNode) int {
		if node == nil {
			return 0
		}

		// 递归计算左子树和右子树的最大路径和（如果小于 0，则不考虑）
		left := max(dfs(node.Left), 0)
		right := max(dfs(node.Right), 0)

		// 更新全局最大路径和
		maxSum = max(maxSum, node.Val + left + right)

		// 返回当前节点的最大路径和
		return node.Val + max(left, right)
	}

	dfs(root)
	return maxSum
}

func main() {
	// 测试用例
	testCases := []struct {
		values   []int
		expected int
	}{
		{
			values:   []int{1,2,3},
			expected: 6,
		},
		{
			values:   []int{-10,9,20,-1,-1,15,7},
			expected: 42,
		},
	}

	for i, tc := range testCases {
		root := createTree(tc.values)
		result := maxPathSum(root)
		fmt.Printf("Test Case %d, Input: root = %v\n", i+1, tc.values)

		if result == tc.expected {
			fmt.Printf("Test Case %d, Output: %d, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %d, FAIL (Expected: %d)\n", i+1, result, tc.expected)
		}
	}
}