哈尔滨多语言网站建设,wordpress分类链接,关于网站建设的电话销售话术,广州天极科技二叉树的最大路径和
难度#xff1a;困难
题目描述
二叉树中的 路径 被定义为一条节点序列#xff0c;序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点#xff0c;且不一定经过根节点。
路径和 是路径中各节点…二叉树的最大路径和
难度困难
题目描述
二叉树中的 路径 被定义为一条节点序列序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root 返回其 最大路径和 。
示例1
输入 root [1,2,3] 输出 6
示例2
输入 root [-10,9,20,null,null,15,7] 输出 42
题解
因为每个节点只能遍历一次所以当选择的根节点不为最顶层的节点的时候叶子节点只能选择一个可以利用回溯算法将两个叶子节点其中的最大值需要大于0和当前节点的和与0进行比较的结果返回回溯结束之后就可以得到最终结果
想法代码
public class TreeNode
{public int val;public TreeNode left;public TreeNode right;public TreeNode(int val 0, TreeNode left null, TreeNode right null){this.val val;this.left left;this.right right;}
}public class Solution
{public static void Main(string[] args){Solution solution new Solution();TreeNode root new TreeNode{val -10,left new TreeNode(9),right new TreeNode{val 20,left new TreeNode(15),right new TreeNode(7)}};int x solution.MaxPathSum(root);Console.WriteLine(x);}public int ans int.MinValue;public int MaxPathSum(TreeNode root){BackTrack(root);return ans;}public int BackTrack(TreeNode root){if (root null){return 0;}int left BackTrack(root.left);int right BackTrack(root.right);int current Math.Max(0, left) Math.Max(0, right) root.val;ans Math.Max(current, ans);return Math.Max(0, Math.Max(left, right)) root.val;}
}
