2021博客--树

这个作业属于哪个班级	数据结构--网络2011/2012
这个作业的地址	DS博客作业03--树
这个作业的目标	学习树结构设计及运算操作
姓名	骆梦钒

0.PTA得分截图

树题目集总得分，请截图，截图中必须有自己名字。题目至少完成2/3，否则本次作业最高分5分。

1.本周学习总结（5分）

学习总结，请结合树的图形展开分析。

1.1 二叉树结构

1.1.1 二叉树的2种存储结构

0.二叉树的性质:

（1）二叉树的第i层上至多有2i-1个节点
（2）深度为K的二叉树至多有2k-1个节点
（3）任何一个二叉树中度数为2的节点的个数必度数为0的节点数目少1.
　　说明:度数为0,为叶子节点。
（4）具有n个节点的完全二叉树的深度为|Log2N|+1
（5）若完全二叉树中的某节点编号为i，则若有左孩子编号为2i，若有右孩子编号为2i+1，母亲节点为i/2。

1.顺序存储结构

·二叉树的顺序存储，指的是使用顺序表（数组）存储二叉树。
需要注意的是，顺序存储只适用于完全二叉树。换句话说，只有完全二叉树才可以使用顺序表存储。因此，如果我们想顺序存储普通二叉树，需要提前将普通二
叉树转化为完全二叉树。

（图 1 中，左侧是普通二叉树，右侧是转化后的完全（满）二叉树。）

·完全二叉树的顺序存储，仅需从根节点开始，按照层次依次将树中节点存储到数组即可。

例如，存储图 2 所示的完全二叉树，其存储状态如图 3 所示：

同样，存储由普通二叉树转化来的完全二叉树也是如此。例如，图 1 中普通二叉树的数组存储状态如图 4 所示：

由此，我们就实现了完全二叉树的顺序存储。

·从顺序表中还原完全二叉树：我们知道，完全二叉树具有这样的性质，将树中节点按照层次并从左到右依次标号（1,2,3,...），若节点 i 有左右孩子，则其左孩子节点为 2i，右孩子节点为 2i+1。此性质可用于还原数组中存储的完全二叉树，也就是实现由图 3 到图 2、由图 4 到图 1 的转变。

2.链式存储结构

·如图 1 所示，此为一棵普通的二叉树，若将其采用链式存储，则只需从树的根节点开始，将各个节点及其左右孩子使用链表存储即可。
因此，图 1 对应的链式存储结构如图 2 所示：

·由图 2 可知，采用链式存储二叉树时，其节点结构由 3 部分构成（如图 3 所示）：
（1）指向左孩子节点的指针（Lchild）；
（2）节点存储的数据（data）；
（3）指向右孩子节点的指针（Rchild）；

·代码

//结构体
typedef struct BiTNode
{
    TElemType data;//数据域
    struct BiTNode *lchild,*rchild;//左右孩子指针
    struct BiTNode *parent;
}BiTNode,*BiTree;

·说明

（1）叶子节点不是没有左右孩子，只不过左右孩子都是空。
（2）我们的二叉树是手动输入数据进行创建的 我在实际开发中不可能是这样创建的，所以我们要处理空节点的问题。
（3）创建和遍历的执行顺序(先序、中序、后序)是一样的，那么输入和取出的值才会是一样的。

·优缺点

（1）完全二叉树最好用数组存放，因为数组下标和父子节点之间存在着完美的对应关系，而且也能够尽最大可能的节省内存。
（2）相比用数组存储数据，链式存储法则相应的更加灵活，我们使用自定义类型Node来表示每一个节点。

1.1.2 二叉树的构造

1.从前序与中序遍历序列构造二叉树

对于任意一颗树而言，前序遍历的形式总是
[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]

即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是
[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]

只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，对上述形式中的所有左右括号进行定位。

这样以来，我们就知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。

class Solution 
{
private:
    unordered_map<int, int> index;

public:
    TreeNode* myBuildTree(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) 
   {
        if (preorder_left > preorder_right)
        {
            return nullptr;
        }
        
        // 前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        // 在中序遍历中定位根节点
        int inorder_root = index[preorder[preorder_root]];
        
        // 先把根节点建立出来
        TreeNode* root = new TreeNode(preorder[preorder_root]);
        // 得到左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        // 递归地构造左子树，并连接到根节点
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root->right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        int n = preorder.size();
        // 构造哈希映射，帮助我们快速定位根节点
        for (int i = 0; i < n; ++i) 
        {
            index[inorder[i]] = i;
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
};

2.从后序与中序遍历序列构造二叉树

我们可以发现后序遍历的数组最后一个元素代表的即为根节点。知道这个性质后，我们可以利用已知的根节点信息在中序遍历的数组中找到根节点所在的下标，然后根据其将中序遍历的数组分成左右两部分，左边部分即左子树，右边部分为右子树，针对每个部分可以用同样的方法继续递归下去构造。

class Solution 
{
    int post_idx;
    unordered_map<int, int> idx_map;
public:
    TreeNode* helper(int in_left, int in_right, vector<int>& inorder, vector<int>& postorder)
    {
        // 如果这里没有节点构造二叉树了，就结束
        if (in_left > in_right) 
        {
            return nullptr;
        }

        // 选择 post_idx 位置的元素作为当前子树根节点
        int root_val = postorder[post_idx];
        TreeNode* root = new TreeNode(root_val);

        // 根据 root 所在位置分成左右两棵子树
        int index = idx_map[root_val];

        // 下标减一
        post_idx--;
        // 构造右子树
        root->right = helper(index + 1, in_right, inorder, postorder);
        // 构造左子树
        root->left = helper(in_left, index - 1, inorder, postorder);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) 
    {
        // 从后序遍历的最后一个元素开始
        post_idx = (int)postorder.size() - 1;

        // 建立（元素，下标）键值对的哈希表
        int idx = 0;
        for (auto& val : inorder) 
        {
            idx_map[val] = idx++;
        }
        return helper(0, (int)inorder.size() - 1, inorder, postorder);
    }
};

1.1.3 二叉树的遍历

1.先序遍历

   访问根结点
   先序遍历左子树
   先序遍历右子树

void PreOrder(BTNode*b)
{
  if(b!=NULL)
  {
printf(“%c”,b->data);
PreOrder(b->lchild);
PreOrder(b->rchild);
  }
}

2.中序遍历

   中序遍历左子树
   访问根结点
   中序遍历右子树

void InOrder(BTNode *b)
{
  if(b!=NULL)
  {
InOrder(b->lchild);
printf(“%c”,b->data);
InOrder(b->child);
  }
}

3.后序遍历

   后序遍历左子树
   后序遍历右子树
   访问根结点

void PostOrder(BTNode *b)
{
  if(b!=NULL)
  {
PostOrder(b->lchild);
PostOrder(b->rchild);
printf(“%c”,b->data);
  }
}

4.层次遍历

每次出队一个元素，就将该元素的孩子节点加入队列中，直至队列中元素个数为0时，出队的顺序就是该二叉树的层次遍历结果。

typedef struct
{
  BTNode *data[MaxSize];
  int front, rear;
}SqQueue;
void LevelOrder(BTNode *b)
{
  BTNode *p;
  SqQueue *qu;//定义环形指针
  InitQueue(qu);//初始化队列
  enQueue(qu,b);//根结点指针进入队列
  while(!QueueEmpty(qu))
  {
deQueue(qu,p);//出队结点p
printf(“%c”,p->data);//访问结点p
if(p->lchild!=NULL)
  enQueue(qu,p->lchild);//进队
if(p->rchild!=NULL)
  enQueue(qu,p->rchild);
  }
}
void LevelOrder(BTNode*b)
{
  queue<BTNode*>que;
  if(b==NULL)
return;
  else
{
  que.push(b);
  while(!que.empty())
  {
    BTNode *b=que.front();
    cout<<b->data<<” “;
    que.pop();
    if(b->lchild!=NULL)
      que.push(b->lchild);
    if(b->rchild!=NULL)
      que.push(b->rchild);
}
}
}

1.1.4 线索二叉树

1.线索二叉树如何设计？

·记ptr指向二叉链表中的一个结点，以下是建立线索的规则：

（1）如果ptr->lchild为空，则存放指向中序遍历序列中该结点的前驱结点。这个结点称为ptr的中序前驱；

（2）如果ptr->rchild为空，则存放指向中序遍历序列中该结点的后继结点。这个结点称为ptr的中序后继；

显然，在决定lchild是指向左孩子还是前驱，rchild是指向右孩子还是后继，需要一个区分标志的。因此，我们在每个结点再增设两个标志域ltag和rtag，注意ltag和rtag只是区分0或1数字的布尔型变量，其占用内存空间要小于像lchild和rchild的指针变量。结点结构如下所示。

·其中：

（1）ltag为0时指向该结点的左孩子，为1时指向该结点的前驱；

（2）rtag为0时指向该结点的右孩子，为1时指向该结点的后继；

（3）因此对于上图的二叉链表图可以修改为下图的养子。

//代码实现
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef struct Binode
{
    char data;
    struct Binode *lchild,*rchild;
    int ltag,rtag;
} Binode,*Bitree;
Bitree pre;
void CreatTREE(Bitree &T)
{
    char ch;
    scanf("%c",&ch);
    if(ch==' ')
    {
        T=NULL;
    }
    else
    {
        T=(Bitree)malloc(sizeof(Binode));
        T->data=ch;
        T->ltag=0;
        T->rtag=0;
        CreatTREE(T->lchild);
        CreatTREE(T->rchild);
    }
    return;
}
void travel_threadtree(Bitree H)     //中序遍历线索树 从头节点开始
{
    Bitree p;
    p=H->lchild;                     //p为二叉树头节点
    while(p!=H)                       
    {
        while(p->ltag==0)            //有左子树 则 一直往下
            p=p->lchild;
        printf("%c ",p->data);       
        while(p->rtag==1&&p->rchild!=H)  //根据它的线索一直往后输出
        {
            p=p->rchild;
            printf("%c ",p->data);
        }
        p=p->rchild;                   //当没有线索时 表示有右子树
    }
    return;
}
void thread(Bitree T)               //线索化
{
    if(T)
    {
        thread(T->lchild);
        if(!T->lchild)
        {
            T->ltag=1;
            T->lchild=pre;
        }
        if(!pre->rchild)
        {
            pre->rtag=1;
            pre->rchild=T;
        }
        pre=T;                    //顺序是左子树 节点 右子树的中序遍历 所有 放这里
        thread(T->rchild);
    }
    return;
}
void threading_(Bitree &H,Bitree T)  //新增头节点
{
    H=(Bitree)malloc(sizeof(Binode));
    H->rchild=H;
    H->rtag=0;
    if(!T)                //二叉树为空
    {
        H->lchild=H;
        H->ltag=0;
    }
    else
    {
        pre=H;
        H->lchild=T;
        H->ltag=0;
        thread(T);
        H->rtag=1;
        H->rchild=pre;   //
        pre->rchild=H;    // 构成循环  以备跳出
    }
    return;
}
int main()
{
    Bitree T,H;
    CreatTREE(T);
    threading_(H,T);
    travel_threadtree(H); 
    return 0;
}

2.中序线索二叉树特点？如何在中序线索二叉树查找前驱和后继？

（1）中序线索二叉树

·头结点左孩子指向根节点
·右孩子为线索，指向最后一个孩子
·遍历序列第一个结点前驱为头结点，最后一个结点后继为头结点

//中序线索遍历二叉树
/*核心思想：*/
/*先找到最左边的节点，然后判断其右子树是否为线索，如果是线索，那么就遍历后继结点，如果右子树是右孩子，那么就进入到右孩子的最左边的节点，进行同样的判断，直到遍历完了整棵树为止。*/
void visit(char c)//访问函数
{
    printf("%c", c);
}
void InorderThr(BiThrTree head)//中序遍历线索二叉树
{
    BiThrTree p=head->lchild;
    while (p != head)//空树或者完成，完成条件是又回到了head
    {
        while (p->ltag == Link)
            p = p->lchild;
        visit(p->data);
        while (p->rtag == Thread&&p->rchild != head)//是线索的话一直找后继线索
        {
            p = p->rchild;
            visit(p->data);
        }
        p = p->rchild;
    }
}

//中序线索化
BiThrTree Pre;//全局变量始终指向刚刚访问的节点
void InThread(BiThrTree &T)//递归中序线索化
{
    if (T)//非空
    {
        InThread(T->lchild);//线索化左孩子
        //处理节点
        if (!T->lchild)//若左孩子空，设置指向前一个访问结点pre的前驱线索
        {
            T->ltag = Thread;
            T->lchild = Pre;//需要设置一个指向刚刚访问的节点
        }
        if (!Pre->rchild)//若前一个结点的右孩子空，设置一个指向本结点T的后继线索
        {
            Pre->rtag = Thread;
            Pre->rchild = T;
        }
        Pre = T;//记录刚刚访问的结点
        InThread(T->rchild);//线索化右孩子
    }
}
void InOrderThreading(BiThrTree &p,BiThrTree &T)//中序线索化函数
{
    p = (BiThrTree)malloc(sizeof(BiThrNode));//创建线索二叉树头结点
    p->ltag = Link;
    p->rtag = Thread;
    p->rchild = p;
    if (!T)//如果空树
        p->lchild = p;
    else//非空树
    {
        p->lchild = T;
        Pre = p;//设置参量，初始化为线索头结点
        InThread(T);
        Pre->rtag = Thread;
        Pre->rchild = p;//最后一个结点的后继为线索头结点
        p->rchild = Pre;//头结点右孩子指向遍历的最后一个结点，形成循环
    }
}

（2）线索二叉树的好处就在于利用了多余的空区域，使之指向前驱或后继，这就使寻找结点的前驱和后继更加方便。

·寻找结点前驱

观察线索二叉树的示意图，如果LTag=1，直接找到前驱，如果LTag=0，则走到该结点左子树的最右边的结点，即为要寻找的结点的前驱。

binThiTree* preTreeNode(binThiTree* q) 
{
	binThiTree* cur;
	cur = q;
	if (cur->LTag == true) 
        {
		cur = cur->lchild;
		return cur;
	}
	else
        {
		cur = cur->lchild;//进入左子树
		while (cur->RTag == false)
                {
			cur = cur->rchild;
		}//找到左子树的最右边结点
		return cur;
	}
}

·寻找结点后继

观察线索二叉树示意图，如果RTag=1，直接找到后继，如果RTag=0，则走到该结点右子树的最左边的结点，即为要寻找的结点的后继。

binThiTree* rearTreeNode(binThiTree* q)
 {
	binThiTree* cur = q;
	if (cur->RTag == true) 
        {
		cur = cur->rchild;
		return cur;
	}
	else
        {
		//进入到*cur的右子树
		cur = cur->rchild;
		while (cur->LTag == false)
                {
			cur = cur->lchild;
		}
		return cur;
	}
}

1.1.5 二叉树的应用--表达式树

1.介绍表达式树如何构造

（1）假设，已知中缀表达式为：（A+B*C）/D，需要获得前缀表达式，后缀表达式.

表达树的前序遍历为前缀表达式，中序遍历为中缀表达式，后续遍历为后缀表达式。
·前缀表达式(前序遍历)：/+ACBD。
·中缀表达式(中序遍历)：A+BC/D。
·后缀表达式(后序遍历)：ACB*+D/。

（2）利用后缀表达式构建表达式树

后缀表达式：ACB*+D/。

为了构建一个表达式树，我们将使用堆栈结构。扫描输入的后缀表达式每一个字符，对每一个字符做如下事情：

（1）如果字符是一个操作数，那么我们就将该操作数存入树节点中，将节点压入（push）堆栈中。

（2）如果字符是一个操作符，那么就从堆栈中压出(pop)两个树节点，构成当前操作符的树节点的左子树和右子树。然后将当前节点压入（push）进堆栈当中。

扫描后缀表达式完毕之后，在堆栈中唯一的节点是表达式树的根节点，我们可以通过根节点遍历整个表达式树。

#include<bits/stdc++.h>

using namespace std;

 

// An expression tree node
struct et
{
    char value;
    et* left, *right;
};
// A utility function to check if 'c'
// is an operator
bool isOperator(char c)
{
    if (c == '+' || c == '-' ||
            c == '*' || c == '/' ||
            c == '^')
        return true;
    return false;
}
// Utility function to do inorder traversal
void inorder(et *t)
{
    if(t)
    {
        inorder(t->left);
        printf("%c ", t->value);
        inorder(t->right);
    }
}
// A utility function to create a new node
et* newNode(int v)
{
    et *temp = new et;
    temp->left = temp->right = NULL;
    temp->value = v;、
    return temp;
};
// Returns root of constructed tree for given
// postfix expression
et* constructTree(char postfix[])
{
    stack<et *> st;
    et *t, *t1, *t2;
    // Traverse through every character of
    // input expression
    for (int i=0; i<strlen(postfix); i++)
    {
        // If operand, simply push into stack
        if (!isOperator(postfix[i]))
        {
            t = newNode(postfix[i]);
            st.push(t);
        }
        else // operator
        {
            t = newNode(postfix[i]);
            // Pop two top nodes
            t1 = st.top(); // Store top
            st.pop();      // Remove top
            t2 = st.top();
            st.pop();
            //  make them children
            t->right = t1;
            t->left = t2;
            // Add this subexpression to stack
            st.push(t);
        }
    }
    //  only element will be root of expression
    // tree
    t = st.top();
    st.pop();
    return t;
}
// Driver program to test above
int main()
{
    char postfix[] = "ab+ef*g*-";
    et* r = constructTree(postfix);
    printf("infix expression is 
");
    inorder(r);
    return 0;
}

2.如何计算表达式树

//计算表达式树
	  public static double caculatePloenTree(treeNode root)
	  {
		  if(!(root.type.equals("+") || root.type.equals("-")||root.type.equals("*")||root.type.equals("-")))
				return Double.parseDouble(root.type);
		  else if(root.type.equals("+"))
		  {
			  return caculatePloenTree(root.lnode) + caculatePloenTree(root.rnode);
		  }
		  else if(root.type.equals("-"))
		  {
			  return caculatePloenTree(root.lnode) - caculatePloenTree(root.rnode);
		  }
		  else if(root.type.equals("*"))
		  {
			  return caculatePloenTree(root.lnode) * caculatePloenTree(root.rnode);
		  }
		  else 
		  {
			  return caculatePloenTree(root.lnode) / caculatePloenTree(root.rnode);
		  }
	  }

1.2 多叉树结构

1.2.1 多叉树结构

1.二叉树中每个结点有一个数据项,最多有两个子节点,如果允许树的每个节点可以有两个以上的子节点,那么这个树就称为n阶的多叉树，或者称为n叉树。

2.多叉树是指一个父节点可以有多个子节点，

但是一个子节点依旧遵循一个父节点定律，通常情况下，二叉树的实际应用高度太高，可以通过多叉树来简化对数据关系的描述。

3.孩子兄弟表示法

从双亲的角度和从孩子的角度研究树的存储结构，如果我们从树节点的兄弟的角度去考虑会怎么样呢？当然，对于树这样的层级结构来说，只研究几点的兄弟是不行的，我们观察后发现，任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。

1.2.2 多叉树遍历

介绍先序遍历做法

N叉树和二叉树类似，不过其指针域是由链表构成，这也就是说不同的节点，指针域的节点数可能是不同的。

思路：类比二叉树的前序遍历，注意节点域的处理。

class Solution 
{
    // private int branch = 0;//没有必要声明为成员变量，声明成成员变量还会出错，成员变量可以被多个递归函数共享，在递归中一层修改，上层下层1都会改变
    private List<Integer> nodeList = new ArrayList<>();
    public List<Integer> preorder(Node root) 
    {
   
        helper(root); 
        return nodeList;
    }
    public void helper(Node root)
    {
        if(root == null)
        {
            return ;
        }
        nodeList.add(root.val);
        int branch = root.children.size();
        for(int i = 0; i < branch; i++)
        {
            helper(root.children.get(i));
        }
        
 
    }
}

//结构体
typedef struct  st_OriTree
{
    int levelValue;    //树的level
    int orderValue;    //排序值
    QString nameValue; //当前节点名称
    QString preNameValue; //前置节点名称
    QMultiMap< int, st_OriTree *> childrenList; //子节点列表
}OriTree;

//创建多叉树
void appendTreeNode(OriTree **head, OriTree node)
{
    if (*head == nullptr)
        return;
    QQueue< OriTree*> queue;
    queue.append(*head);

    bool isExist = false;
    OriTree* p = nullptr;
    OriTree* q = *head;
    while (!queue.isEmpty())
    {
        p = queue.front();
        queue.pop_front();
        if (p != nullptr)
        {
            for (int i = 0; i < p->childrenList.count(); i++)
            {
                if (p->childrenList.values().at(i)->preNameValue == node.preNameValue
                    && p->childrenList.values().at(i)->levelValue == node.levelValue)
                {
                    if (p->childrenList.values().at(i)->nameValue == node.nameValue)
                    {
                        isExist = true;
                        break;
                    }
                    continue;
                }
                if (p->childrenList.values().at(i)->levelValue == node.levelValue - 1
                    && p->childrenList.values().at(i)->nameValue == node.preNameValue)
                {
                    q = p->childrenList.values().at(i);
                }
                queue.append(p->childrenList.values().at(i));
            }
        }
    }
    if (!isExist && q!= nullptr)
    {
        //create new node
        OriTree * newNode = new OriTree();
        if (newNode == nullptr || p == nullptr)
        {
            qDebug() << "new OriTree node failed , node Name :" << node.nameValue;
            return;
        }
        newNode->feedValue = node.feedValue;
        newNode->levelValue = node.levelValue;
        newNode->nameValue = node.nameValue;
        newNode->orderValue = node.orderValue;
        newNode->preNameValue = node.preNameValue;
        Q_ASSERT(q->feedValue == nullptr);
        if (q->feedValue != nullptr)
        {
            qDebug() << "new OriTree build tree error, node Name" << node.nameValue;
            return;
        }
        q->childrenList.insert(node.orderValue, newNode);
    }
}

//层次优先遍历多叉树结构（利用队列实现）
void travel( OriTree * tree)
{
    if (tree == nullptr)
        return;

    QQueue<OriTree*> qTree;
    qTree.append(tree);

    OriTree* p = nullptr;
    while (!qTree.isEmpty())
    {
        p = qTree.front();
        qTree.pop_front();
        if (p != nullptr)
        {
            for (int i = 0; i < p->childrenList.count(); i++)
            {
                qDebug() << p->childrenList.values().at(i)->nameValue;
                qTree.append(p->childrenList.values().at(i));
            }
        }
    }
}

//层次深度优先遍历
void travel(OriTree * tree)
{
    pathQueue.append(tree);
    if (tree == nullptr || tree->childrenList.values().count() == 0)
    {
        //一条路径遍历完毕,此时pathQueue为完整的节点路径
        qDebug() << pathQueue.size();
        //将最后入队的节点pop
        pathQueue.pop_back();
        return;
    }
    for (int i = 0; i < tree->childrenList.values().count(); i++)
    {
        BuildTreeItem(tree->childrenList.values().at(i));
        if (i == tree->childrenList.values().count() - 1)
        {
            pathQueue.pop_back(); //当前节点 pop
        }
    }
}

1.3 哈夫曼树

1.3.1 哈夫曼树定义

什么是哈夫曼树？，哈夫曼树解决什么问题？

1.定义

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

2.应用

（1）哈夫曼编码

利用哈夫曼树来设计二进制的前缀编码，既满足前缀编码的条件，又保证报文编码总长最短。

（2）哈夫曼译码

在通信中，若将字符用哈夫曼编码形式发送出去，对方接收到编码后，将编码还原成字符的过程，称为哈夫曼译码。

1.3.2 哈夫曼树的结构体

教材是顺序存储结构，也可以自己搜索资料研究哈夫曼的链式结构设计方式。

struct node
{
	int val;	//记录权值 
	node *self = NULL;	//存自己的节点 
	node *left = NULL;	//左子节点 
	node *right = NULL;	//右子节点 
	bool operator < (const node &b)const
        {
		return val > b.val;
	}
};

1.3.3 哈夫曼树构建及哈夫曼编码

结合一组叶子节点的数据，介绍如何构造哈夫曼树及哈夫曼编码。

第一部分;由给定结点构造哈夫曼树

（1）8个结点的权值大小如下：

（2）从19，21，2，3，6，7，10，32中选择两个权小结点。选中2，3。同时算出这两个结点的和5。

（3）从19，21，6，7，10，32，5中选出两个权小结点。选中5，6。同时计算出它们的和11。

（4）从19，21，7，10，32，11中选出两个权小结点。选中7，10。同时计算出它们的和17。

（BTW：这时选出的两个数字都不是已经构造好的二叉树里面的结点，所以要另外开一棵二叉树；或者说，如果两个数的和正好是下一步的两个最小数的其中的一个，那么这个树直接往上生长就可以了，如果这两个数的和比较大，不是下一步的两个最小数的其中一个，那么就并列生长。）

（5）从19，21，32，11，17中选出两个权小结点。选中11，17。同时计算出它们的和28。

（6）从19，21，32，28中选出两个权小结点。选中19，21。同时计算出它们的和40。另起一颗二叉树。

（7）从32，28， 40中选出两个权小结点。选中28，32。同时计算出它们的和60。

（8）从 40， 60中选出两个权小结点。选中40，60。同时计算出它们的和100。 好了，此时哈夫曼树已经构建好了。

第二部分：由上述所得哈夫曼树写出哈夫曼编码

首先我们来看这棵构造好的哈夫曼树：（经过左边路径为0，经过右边路径为1）

则可直接写出编码，例如：

A:11   B:001    C:011  D   E：0000    F：0001    G：0100    H：0101    I：1000   J：1001

为了简便起见，我们从树的左边开始考虑，即B,E,F节点。

对于节点B，其深度为3，权值为5，那么其带权路径长度为5*3 = 15；

那么我们再看一下节点B的父亲节点，其权值为9，是由权值为4和权值为5的节点B构造而成，那么即是9 = 4 + 5；

同样的再往上一层，节点B的爷爷节点，其权值为16，是由权值为9和权值为7的节点构造而成，而权值为9的节点的构造前面已经说明，则有16 = 4 + 5 + 7；

再往上一层就到根节点了。

那么到这里我们可以看到，节点B的父亲节点和爷爷节点的组成部分都有节点B的“功劳”，即节点B的权值是其另外两个的“组成部分”，那么节点B的带权路径长度即为其到根节点路径上（不包含根节点），与其（或者说是与其父节点，爷爷节点等）有父子关系的节点抽取出节点B的组成部分（包括节点B本身），再全部相加，这样的话就得到了节点B的带权路径长度为5 + 5 + 5 = 15；

同样的，节点E,F按照同样的方法进行推导。

所以我们从上面的分析得出：

每个带权叶节点到根节点的带权路径长度等于其到根节点路径上所有节点的包含该带权叶节点权值组成部分之和。

因此，最后我们推导出，所有叶节点，即整棵哈夫曼树的带权路径长度 WPL即为：

除了根节点以外，所有节点的权值之和。

如上图哈夫曼树的带权路径长度 WPL即为：

WPL = 16 + 10 + 9 + 7 + 5 + 5 + 4 + 5 + 3 + 4 + 2 + 3 + 2 + 2 + 2 + 1 + 1 + 1 = 82

有了这样的判断之后，我们便很容易计算出一颗哈夫曼树的带权路径WPL了。

因此我们可以借助一个叫做优先队列的数据结构，而优先队列的实现往往是借助于二叉堆的结构实现，在这里我们要实现的是小根堆的数据结构。一开始的时候，我们可以将所有的节点一个一个的压入队列中，每次有节点入队，队列都会进行自调整，使其保持一个小根堆的状态。当所有的节点全部入队之后，这时候我们根据以上推导出来的结论，每次取两个权值最小的节点，将其值计算之后，然后再将两个节点权值之和的节点压入队列中，直到队列中只剩下一个节点（即根节点），跳出循环体，输出最后的答案。即整棵哈夫曼树的带权路径WPL。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

//树结点定义
typedef  struct 
{
    int weight;
    int parent;
    int lchild;
    int rchild;
}HTNode,*HuffmanTree;

static char N[100];//用于保存正文

//哈弗曼编码，char型二级指针
typedef char **HuffmanCode;

//封装最小权结点和次小权结点
typedef  struct 
{
    int s1;
    int s2;
}MinCode;

//函数声明
void Error(char *message);
HuffmanCode HuffmanCoding(HuffmanTree &HT,HuffmanCode HC,int *w,int n);
MinCode   Select(HuffmanTree HT,int n);

//当输入1个结点时的错误提示
void Error(char *message)
{  
    fprintf(stderr,"Error:%s
",message);  
    exit(1);
}

//构造哈夫曼树HT，编码存放在HC中,w为权值,n为结点个数
HuffmanCode HuffmanCoding(HuffmanTree &HT,HuffmanCode HC,int *w,int n)
{ 
    int i,s1=0,s2=0; 
    HuffmanTree p;
    char *cd;
    int f,c,start,m;
    MinCode min;

    if(n<=1) 
    {
        Error("Code too small!");//只有一个结点不进行编码，直接exit(1)退出。非return,如果return 会造成main函数HT[i]无值
    }

    m=2*n-1;//哈弗曼编码需要开辟的结点大小为2n-1
    HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//开辟哈夫曼树结点空间 m+1 。为了对应关系，我们第0个空间不用。

    //初始化n个叶子结点,w[0] = 0,main函数已赋值
    for(p=HT,i=0;i<=n;i++,p++,w++)
    { 
        p->weight=*w;  
        p->parent=0; 
        p->lchild=0; 
        p->rchild=0;
    }

    //将n-1个非叶子结点的初始化
    for(;i<=m;i++,p++)
    { 
        p->weight=0;  
        p->parent=0; 
        p->lchild=0;
        p->rchild=0;
    }

    //构造哈夫曼树
    for(i=n+1;i<=m;i++)
    {
        min=Select(HT,i-1);//找出最小和次小的两个结点
        s1=min.s1 ; //最小结点下标
        s2=min.s2;//次小结点下标
        HT[s1].parent=i; 
        HT[s2].parent=i;
        HT[i].lchild=s1;
        HT[i].rchild=s2;
        HT[i].weight=HT[s1].weight+HT[s2].weight;//赋权和
    }

    //打印哈弗曼树
    printf("HT  List:
");
    printf("Number		weight		parent		lchild		rchild
");

    for(i=1;i<=m;i++)
    {
        printf("%d		%d		%d		%d		%d	
",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
    }

    //从叶子结点到根节点求每个字符的哈弗曼编码
    HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
    cd=(char *)malloc(n*sizeof(char *));//为哈弗曼编码动态分配空间
    cd[n-1]='';//如：3个结点编码最长为2。cd[3-1] = '';

    //求叶子结点的哈弗曼编码
    for(i=1;i<=n;i++)
    { 
        start=n-1;
        //定义左子树为0，右子树为1
        /*
        从最下面的1号节点开始往顶部编码(逆序存放)，然后编码2号节点，3号......
        */
        for(c=i,f=HT[i].parent; f!=0; c=f,f=HT[f].parent)
        {
            if(HT[f].lchild==c)  
                cd[--start]='0';
            else 
                cd[--start]='1';
        }

        //为第i个字符分配编码空间
        HC[i]=(char *)malloc((n-start)*sizeof(char *));
        //将当前求出结点的哈弗曼编码复制到HC
        strcpy(HC[i],&cd[start]);   
    }
    free(cd);
    return HC;
}

MinCode Select(HuffmanTree HT,int n)
{  
    int min,secmin;
    int temp = 0;
    int i,s1,s2,tempi = 0;
    MinCode  code ;
    s1=1;
    s2=1;

    min = 66666;//足够大

    //找出权值weight最小的结点，下标保存在s1中
    for(i=1;i<=n;i++)
    {
        if(HT[i].weight<min && HT[i].parent==0)
        {
            min=HT[i].weight;
            s1=i;
        }
    }

    secmin = 66666;//足够大

    //找出权值weight次小的结点，下标保存在s2中
    for(i=1;i<=n;i++)
    {
        if((HT[i].weight<secmin) && (i!=s1) && HT[i].parent==0)
        {
            secmin=HT[i].weight; 
            s2=i;
        }
    }

    //放进封装中
    code.s1=s1;
    code.s2=s2;
    return code;
}

void HuffmanTranslateCoding(HuffmanTree HT, int n,char* ch)
{//译码过程
    int m=2*n-1;
    int i,j=0;

    printf("After Translation:");
    while(ch[j]!='')//ch[]:你输入的要译码的0101010串
    {
        i=m;
        while(0 != HT[i].lchild && 0 != HT[i].rchild)//从顶部找到最下面
        {
            if('0' == ch[j])//0 往左子树走
            {
                i=HT[i].lchild;
            }
            else//1 往右子树走
            {
                i=HT[i].rchild;
            }
            ++j;//下一个路径
        }
        printf("%c",N[i-1]);//打印出来
    }
    printf("
");
}

void main()
{
    HuffmanTree HT=NULL;
    HuffmanCode HC=NULL;
    int *w=NULL;
    int i,n;
    char tran[100];

    printf("Input  N(char):");
    gets(N);
    fflush(stdin);
    n = strlen(N);

    w=(int *)malloc((n+1)*sizeof(int *));//开辟n+1个长度的int指针空间
    w[0]=0;
    printf("Enter weight:
");

    //输入结点权值
    for(i=1;i<=n;i++)
    {  
        printf("w[%d]=",i);  
        scanf("%d",&w[i]);
    }
    fflush(stdin);
    //构造哈夫曼树HT，编码存放在HC中,w为权值,n为结点个数
    HC=HuffmanCoding(HT,HC,w,n);

    //输出哈弗曼编码
    printf("HuffmanCode:
");
    printf("Number		Weight		Code
");
    for(i=1;i<=n;i++)
    {
        printf("%c		%d		%s
",N[i-1],w[i],HC[i]);
    }

    fflush(stdin);
    //译码过程
    printf("Input HuffmanTranslateCoding:");
    gets(tran);
    HuffmanTranslateCoding(HT, n, tran);
    return;
}

1.4 并查集

1.什么是并查集？

并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。常常在使用中以森林来表示。

2.并查集解决什么问题，优势在哪里？

并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中。其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能用并查集来描述。

3.并查集的结构体、查找、合并操作如何实现？

合并：合并两个集合；
查找：判断两个元素是否为在一个集合
性质：并查集产生的每一个集合都是一棵树

//结构体
#define MAX 10000
struct Node
{
    int parent; // 集合index的类别
    int data;   // 集合index的数据类型
    int rank;   // 集合index的层次，通常初始化为0
 }node[MAX];

//初始化
void Init(int father[], int n)
{
    for (int i = 0; i <= n; ++i)
    {
        father[i] = i;
    }
}

//查找
int findFather(int x)
{
    while(x != father[x])
    {
        x = father[x];
    }
    return x;
}

int findFather2(int x)
{
    if(x == father[x]) return x;
    else return findFather2(father[x]);
}

//路径压缩
int findFather3(int x)
{
    inx
    //x存放根结点，把路径上所有结点的father都改为根结点

    while(a != father[a])
    {
        int z = a;  //现保存a的值
        a = father[a];//a回朔父亲结点
        father[z] = x;//将原先结点a的父亲改为根结点x
    }

    return x;//返回根结点
}

int findFather4(int v)
{
    if(v == father[v]) return v;
    else
    {
        int F = findFather4(father[v]);
        father[v] = F;
        return F;
    }
}

//合并
void Union(int a, int b)
{
    int faA = findFather(a);
    int faB = findFather(b);
    if(faA != faB)
    {
        father[faA] = faB;
    }
}

1.5.谈谈你对树的认识及学习体会。

1.树的内容较多，所以在这里总结一下

·树的定义：

树是由 n (n ≥ 0) 个结点组成的有限集合。如果 n = 0，称为空树；如果 n > 0，则有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱；除根以外的其他结点划分为 m (m ≥ 0) 个 互不相交的有限集合T0, T1, …, Tm-1，每个集合又是一棵树，并且称之为根的子树。

·树的特点：

每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。

·树的一些基本概念：

结点：存储数据元素和指向子树的链接，由数据元素和构造数据元素之间关系的引用组成。
孩子结点：树中一个结点的子树的根结点称为这个结点的孩子结点。
双亲结点：树中某个结点有孩子结点(即该结点的度不为0)，该结点称为它孩子结点的双亲结点，也叫前驱结点。
兄弟结点：具有相同双亲结点(即同一个前驱)的结点称为兄弟结点。
结点的度：结点所有子树的个数称为该结点的度。
树的度：树中所有结点的度的最大值称为树的度。
叶子结点：度为0的结点称为叶子结点，也叫终端结点。
分支结点：度不为0的结点称为分支结点，也叫非终端结点。
结点的层次：从根结点到树中某结点所经路径的分支数称为该结点的层次。根结点的层次一般为1(也可以自己定义为0)，这样，其它结点的层次是其双亲结点的层次加1.
树的深度：树中所有结点的层次的最大值称为该树的深度(也就是最下面那个结点的层次)。
有序树和无序树：树中任意一个结点的各子树按从左到右是有序的，称为有序树，否则称为无序树。

·二叉树的定义：

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。

·满二叉树的定义：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。

·完全二叉树的定义：若设二叉树的高度为h，则共有h+1层。除第 h 层外，其它各层 (0 ~h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。（这里加粗的文字隐含了n-1层二叉树节点只允许出现右孩子缺省或左右都缺的含义）

·完美二叉树定义：满足完全二叉树性质，树的叶子节点均在最后一层。

·理想平衡二叉树：任意两个叶节点的深度之差不超过1，即任意节点左右子树深度之差绝对值不超过1。

·二叉树的性质：

1）若二叉树的层次从0开始, 则在二叉树的第 i 层最多有 2^i 个结点。(i >= 0)。
2）高度为 h 的二叉树最多有 2^(h+1)-1个结点。(h >= -1)
3）对任何一棵二叉树, 如果其叶结点有 n0 个, 度为2的非叶结点有 n2 个, 则有n0＝n2＋1。
4）具有 n (n >= 0) 个结点的完全二叉树的高度为log2(n+1) -1.
5）如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号0, 1, 2, …, n-1，则有以下关系：
若i = 0, 则 i 无双亲
若i > 0, 则 i 的双亲为(i -1)/2
若2i+1 < n, 则 i 的左子女为 2i+1
若2i+2 < n, 则 i 的右子女为2i+2
若 i 为偶数, 且i != 0, 则其左兄弟为i-1
若i 为奇数, 且i != n-1,则其右兄弟为i+1

·二叉树存储
链式存储+顺序存储

·二叉树的遍历（必考）
树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次
先序遍历、中序遍历、后序遍历

·哈夫曼树

哈夫曼树是一种带权路径长度最短的二叉树，也称为最优二叉树。那么问题来了，什么是路径，什么是带权路径呢？那么下面给出几个基本概念。
路径：树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。
路径长度：路径上的分枝数目称作路径长度。
树的路径长度PL：从树根到每一个结点的路径长度之和。
结点的带权路径长度：在一棵树中，如果其结点上附带有一个权值，通常把该结点的路径长度与该结点上的权值之积成为带权路径。
树的带权路径长度WPL：如果树中每个叶子上都带有一个权值，则把树中所有叶子的带权路径长度之和称为树的带权路径长度。

2.PTA实验作业（4分）

此处请放置下面2题代码所在码云地址(markdown插入代码所在的链接)。如何上传VS代码到码云

2.1 二叉树

输出二叉树每层节点

2.1.1 解题思路及伪代码

1.解题思路

运用两个指针记住当前结点位置和每层的最后一个结点位置，以便于当当前结点等于层最后结点时，输出换行并输出下一层结点；
而每层的结点都要通过队列依次存入并且依次输出。

2.伪代码

void LayerNode(BTree bt)//输出层节点
定义layer等于1表示输出的层数
定义flag用于判断是否为第一层结点
定义一个BTree型的队列qtree，用于存放结点
定义tNode，node和lastNode指针分别用于存放遍历中途结点的孩子结点，此时遍历到的结点和下一层要的最够一个结点
node=lastNode=bt
if bt不为空 
  do
    bt入队列
else 
  do
    输出NULL并返回
end 
while 队列qtree不为空 
  do
    if flag=0 
      do 
        输出“1:”,并将flag置为1  //即只在第一次循环时输出1
    end 
    node取队列qtree的front
    if node->rchild 
      do 
        将node->rchild赋值给tNode
    else if node->lchild 
      do
        将node->lchild赋值给tNode /*先判断右结点是为了保证下一层最后一个结点在右孩子结点，若不在，则再判断左孩子*/
    end 
    输出node->data
    并将node的左右孩子入队  //实现层层的遍历
    将node结点出队
    if node=lastNode and 队列不为空 
      do
        换行再输出++layer //即下面输出的是下一层结点
        lastNode = tNode  //将下一层最右边的孩子结点赋值给lastNode
    end 
end

2.1.2 总结解题所用的知识点

（1）运用队列的知识对每层结点进行存入与输出
（2）递归调用函数
（3）通过层层遍历，设置结点使遍历到每层的最后一个结点时将一层结点输出
（4）用flag控制输出格式
（5）测试数据发现当每一层最后结点不在上一层最后结点的右结点，则答案会出现错误；解决方法是记录上一层每个结点最靠右边的结点，在要进入下一层结点遍历时赋值给lastNode即可

2.2 目录树

2.2.1 解题思路及伪代码

1.解题思路

先设计目录树结构体，进行初始化树；建立孩子兄弟链的结构，读入字符串并分离，判断是文件还是目录，分别进入各自的函数，文件函数通过对比优先级的高低，若高则改变指针的位置原来位置变为其孩子，低则作为孩子插入，相同则在其当前位置基础上进行操作，目录函数则是对兄弟链进行操作。

2.伪代码

void InitList(Tree& temp, Tree& bt)//插入目录
{
    定义结构体指针btr来遍历二叉树bt；
        btr = bt->child;//btr先指向bt的孩子；

        /*先对第一个兄弟结点进行判断*/
    if 没有第一个孩子或 btr为文件 或 第一个孩子字典序大于该结点//可插入
        进行插入temp->brother = btr;bt->child = temp;//修改孩子指针
    else if 相等
        直接使temp指向btr；
    else //查找兄弟节点
        while btr->brother 不等于 NULL
            if 兄弟节点为文件 或 兄弟节点字典序大于该节点
                找到可插入位置，break；
            else if 相等
                直接使temp指向btr->brother;break;
            else
                btr = btr->brother;//遍历下一兄弟结点；
    end if
        end while
        if btr->brother为空 或 btr->brother->name != temp->name
            进行插入操作:temp->brother = btr->brother;btr->brother = temp;
    end if
        end if
}

void InitFile(Tree& temp, Tree& bt)//对文件temp找一个可插入位置
{
    定义结构体指针btr来遍历二叉树bt；
        btr = bt->child;//btr先指向bt的孩子；

    if 第一个孩子为空 或 btr为文件 且 结点字典序大于等于该节点
        进行插入，修改bt的孩子指针；
    else //判断兄弟结点
        while btr->brother 不等于 NULL
            if btr->brother为文件 且 兄弟节点字典序大于该节点
                找到可插入位置，break;
            else
                btr = btr->brother;//遍历下一个兄弟结点
    end if
        end while
        对temp进行插入操作:temp->brother = btr->brother;btr->brother = temp;
    end if
}

2.2.2 总结解题所用的知识点

（1）使用到孩子兄弟链结构
（2）结构体中增加isfile判断一个结点是目录还是文件
（3）需要考虑是否有第一个孩子，孩子是目录还是文件，二者字典序大小等情况
（4）插入的顺序要求：目录在文件前面，字典序小的在前面

3.阅读代码（0--1分）

3.1 题目及解题代码

1.题目

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

class Solution {
private:
    int maxSum = INT_MIN;

public:
    int maxGain(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }
        
        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = max(maxGain(node->left), 0);
        int rightGain = max(maxGain(node->right), 0);

        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = node->val + leftGain + rightGain;

        // 更新答案
        maxSum = max(maxSum, priceNewpath);

        // 返回节点的最大贡献值
        return node->val + max(leftGain, rightGain);
    }

    int maxPathSum(TreeNode* root) {
        maxGain(root);
        return maxSum;
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/er-cha-shu-zhong-de-zui-da-lu-jing-he-by-leetcode-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

3.2 该题的设计思路及伪代码

1.设计思路

首先，考虑实现一个简化的函数 maxGain(node)，该函数计算二叉树中的一个节点的最大贡献值，具体而言，就是在以该节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值之和最大。

具体而言，该函数的计算如下。

·空节点的最大贡献值等于 0。
·非空节点的最大贡献值等于节点值与其子节点中的最大贡献值之和（对于叶节点而言，最大贡献值等于节点值）。

根据函数 maxGain 得到每个节点的最大贡献值之后，如何得到二叉树的最大路径和？对于二叉树中的一个节点，该节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值，如果子节点的最大贡献值为正，则计入该节点的最大路径和，否则不计入该节点的最大路径和。维护一个全局变量 maxSum 存储最大路径和，在递归过程中更新 maxSum 的值，最后得到的 maxSum 的值即为二叉树中的最大路径和。

2.伪代码

定义maxSum=INT_MIN
int maxGain（TreeNode*node）
{
  if node==NULL
then
  return 0
 // 递归计算左右子节点的最大贡献值
 // 只有在最大贡献值大于 0 时，才会选取对应子节点
  定义leftGain=max（maxGain（node->left）,0）
  定义rightGain=max（maxGain（node->right）,0）
// 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
  定义priceNewpath=node->val+leftGain+rightGain
  maxSum=max(maxSum,priceNewpath)
  返回node->val+max(leftGain,rightGain)
}
int maxPathSum(TreeNode*root)
{
  maxGain(root)
  返回maxSum
}

3.复杂度分析

时间复杂度：O(N)O(N)，其中 NN 是二叉树中的节点个数。对每个节点访问不超过 22 次。

空间复杂度：O(N)O(N)，其中 NN 是二叉树中的节点个数。空间复杂度主要取决于递归调用层数，最大层数等于二叉树的高度，最坏情况下，二叉树的高度等于二叉树中的节点个数。

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

3.3 分析该题目解题优势及难点。

（1）这题目的难点在于理解题意和转化题意

（2）对于二叉树中的一个节点，该节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值，于是可以通过维护一个全局变量 maxSum 存储最大路径和

（3）对每个结点访问次数不超过两次，提升效率

（4）要时刻记得递归函数的功能，该题中递归函数maxGain的功能是获取以当前节点开始的最大路径和，处理递归只需要处理好递归出口和return返回值即可，然后以该递归函数的功能直接调用它。而求该题所获取的答案在递归函数中更新是因为恰巧递归函数中遍历到当前节点时可以获取左右子树的最大路径和，因此可以在此处计算下获得题目要求的答案，这也是为什么更新的是一个全局变量。