赞
踩
给定一个非空二叉树,返回其最大路径和。
本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。、
思路:
这道题,首先要正确理解题目意思。返回一个最大路径和,很容易想到用递归地方法,将子节点的路径和求出,加上自身就是该节点为根的路径和。题目的要求是从任意节点出发,而不是子树的根节点出发,因此要将左右子树的路径和都加上才符合题意。
当然,计算中需要判断左右子树路径和加自身节点值是否变小(也就是子树路径小于0)
int sum_max =INT_MIN; int maxPathSum(TreeNode* root) { int ans = 0; //深先用优先搜索吧 dfs(root); return sum_max; } int dfs(TreeNode* node) { if(node == nullptr) { return 0; } int val = node->val; int sum_left = dfs(node->left); int sum_right = dfs(node->right); int sum_all = val+sum_left+sum_right; val = max(max(val+sum_left, val + sum_right), val); int sum = max(val, sum_all); sum_max = max(sum, sum_max); return val; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。