二叉树之求二叉树中最大路径和

朱雀 2023-02-14 10:41 152阅读 0赞

LeetCode中一道求二叉树中最大路径和的题目，一起来复习下二叉树的遍历。以如图所示二叉树为例  
![在这里插入图片描述][2020060215091962.bmp]  
1、二叉树前序遍历 根-》左子树-》右子树

void PreorderErgodic(TwoTree* p)
    {
        
       if (p != NULL)
       {
        
           printf("%d,",p->value);
           PreorderErgodic(p->left);
           PreorderErgodic(p->right);
       }
    }
    //1,2,3,4,5,6,7,8,9,10,11,

2、二叉树中序遍历 左子树-》根-》右子树

void MiddleOrderErgodic(TwoTree* p)
    {
        
        if (p != NULL)
        {
        
            MiddleOrderErgodic(p->left);
            printf("%d,",p->value);
            MiddleOrderErgodic(p->right);
        }
    }
    //4,3,2,6,5,8,7,1,10,9,11,

3、 二叉树后序遍历 左子树-》右子树-》根

void PostorderErgodic(TwoTree* p)
    {
        
        if (p != NULL)
        {
        
            PostorderErgodic(p->left);
            PostorderErgodic(p->right);
            printf("%d,",p->value);
        }
    }
    //4,3,6,8,7,5,2,10,11,9,1,

4、现在我来看看求最大路径和，求最大，当然是要对比左右子树最大一个，然后加上自己。代码如下

int MaxPath(TwoTree* p)
    {
        
        if (NULL == p)
        {
        
            return 0;
        }
        int left = MaxPath(p->left);
        int right = MaxPath(p->right);
        return max(left, right) + p->value;
    }
    //23   8-》7-》5-》2-》1

可以看出，这是个后序遍历，先分别遍历左子树、右子树，对比最大子树值，返回最大子树+自己的值。

[2020060215091962.bmp]: https://img-blog.csdnimg.cn/2020060215091962.bmp

发表评论取消回复

表情：

评论列表（有 0 条评论，152人围观）

还没有评论，来说两句吧...

相关阅读

相关二叉树——654. 最大二叉树

1 题目描述给定一个不重复的整数数组nums。最大二叉树可以用下面的算法从nums递归地构建: 1.创建一个根节点，其值为nums中的最大值。 2.递归地在最大

短命女/ 2023年10月08日 16:13/ 0 赞/ 7 阅读

相关 LeetCode_二叉树_困难_124. 二叉树中的最大路径和

目录 1.题目 2.思路 3.代码实现（Java） 1.题目路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一

港控/mmm°/ 2023年10月06日 22:43/ 0 赞/ 22 阅读

相关二叉树中的最大路径和

二叉树中的最大路径和 -------------------- 路径和：二叉树的任意两节点经过中间若干节点（当然也可能中间没有节点，另外单个节点也可看作路径，这里理解

本是古典何须时尚/ 2023年02月20日 02:53/ 0 赞/ 101 阅读

相关二叉树之求二叉树中最大路径和

LeetCode中一道求二叉树中最大路径和的题目，一起来复习下二叉树的遍历。以如图所示二叉树为例 ![在这里插入图片描述][2020060215091962.bmp]

朱雀/ 2023年02月14日 10:41/ 0 赞/ 153 阅读

相关二叉树中的最大路径和

一、前言里面来源LeetCode 124，难度：困难问题链接：[https://leetcode-cn.com/problems/binary-tree-maxim

缺乏、安全感/ 2023年02月10日 03:55/ 0 赞/ 12 阅读

相关 124. 二叉树中的最大路径和

题目： [124. 二叉树中的最大路径和][124.] [\[编程题\]二叉树的最大路径和][Link 1] ![在这里插入图片描述][watermark_typ

淩亂°似流年/ 2022年12月11日 12:26/ 0 赞/ 178 阅读

相关二叉树中的最大路径和

二叉树中的最大路径和 1、参考资料 https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/

亦凉/ 2022年12月03日 11:25/ 0 赞/ 182 阅读

相关二叉树最大路径和

给定一个非空二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。 public

待我称王封你为后i/ 2022年10月27日 00:29/ 0 赞/ 197 阅读

相关二叉树求最短路径

include<iostream> include<stdlib.h> using namespace std; template <class

痛定思痛。/ 2022年06月14日 10:22/ 0 赞/ 250 阅读

相关求二叉树的最大路径和

![这里写图片描述][70] //二叉树节点的定义 class TreeNode { int val; TreeNod

古城微笑少年丶/ 2022年05月20日 05:15/ 0 赞/ 211 阅读