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

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

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

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

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

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

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

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

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

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

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

发表评论

表情：
评论列表 （有 0 条评论，189人围观）

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

相关阅读