算法笔记（十三）—— 树形DP及Morris遍历

树形DP：

 

Question1: 

 以X为头结点的树，最大距离：

1. X不参与，在左子树上的最大距离

2. X不参与，在右子树上的最大距离

3. X参与，左树上最远的结点通过X到右树最远的结点

最后的结果一定是三种情况的最大值

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Info{public:int maxdistace;int high;Info(int val1 , int val2){maxdistace = val1;high = val2;}
};class Solution {
public:Info dp(TreeNode* node){if(node==nullptr){return Info(0,0);}Info l = dp(node->left);Info r= dp(node->right);return Info(max(l.high+r.high+1 , max(l.maxdistace , r.maxdistace)) , max(l.high,r.high)+1);}int diameterOfBinaryTree(TreeNode* root) {Info res = dp(root);return res.maxdistace-1;}
};

Question2: 

 根据某树头结点来或不来进行分类即可

#include <iostream>
#include<bits/stdc++.h>
using namespace std;class TreeNode{
public:int num;int happy;vector<TreeNode*> nexts;TreeNode(int number , int val){num = number;happy = val;}
};class Info{
public:int inval;int outval;Info(int val1 , int val2){inval = val1;outval = val2;}
};vector<TreeNode*> Happy;Info dp(int cur){if(Happy[cur]->nexts.empty())return Info(Happy[cur]->happy , 0);int inv = Happy[cur]->happy;int outv = 0;for(auto &it:Happy[cur]->nexts){Info temp = dp(it->num);inv += temp.outval;outv += max(temp.inval , temp.outval);}return Info(inv , outv);
}int main() {int n , root;cin>>n>>root;Happy.resize(n);for(int i = 1 ; i<=n ; i++){int val;cin>>val;Happy[i-1] = new TreeNode(i-1 , val);}for(int i = 0 ; i<n-1 ; i++){int up , low;cin>>up>>low;Happy[up-1]->nexts.push_back(Happy[low-1]);}Info res = dp(root-1);cout<<max(res.inval , res.outval);return 0;
}

Morris遍历(时间复杂度O(N) 空间复杂度O(1))

前序：第一次到达一个节点的时候就打印

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> res;if(root==nullptr)return res;while(root!=nullptr){TreeNode* temp = root->left;if(temp!=nullptr){while(temp->right!=nullptr&&temp->right!=root){temp = temp->right;}if(temp->right==nullptr){temp->right = root;res.push_back(root->val);root = root->left;continue;}else{temp->right = nullptr;}}else{res.push_back(root->val);}root = root->right;}return res;}
};

中序：只能到达一次的节点直接打印，能到达两次的第二次打印

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> res;if(root==nullptr)return res;while(root!=nullptr){TreeNode* temp = root->left;if(temp!=nullptr){while(temp->right!=nullptr&&temp->right!=root){temp = temp->right;}if(temp->right==nullptr){temp->right = root;root = root->left;continue;}else{temp->right = nullptr;}}res.push_back(root->val);root = root->right;}return res;}
};

后序：第二次回到一个节点时，逆序打印该节点左子树，右边界，最后单独逆序打印整棵树右边界

class Solution {
public:TreeNode* reverse(TreeNode* root){TreeNode* pre = nullptr;TreeNode* next = nullptr;while(root!=nullptr){next = root->right;root->right = pre;pre = root;root = next;}return pre;}vector<int> postorderTraversal(TreeNode* root) {vector<int> res;TreeNode* head = root;if(root==nullptr)return res;while(root!=nullptr){TreeNode* temp = root->left;if(temp!=nullptr){while(temp->right!=nullptr&&temp->right!=root){temp = temp->right;}if(temp->right==nullptr){temp->right = root;root = root->left;continue;}else{temp->right = nullptr;TreeNode* cur = reverse(root->left);TreeNode* temp = cur;while(temp!=nullptr){res.push_back(temp->val);temp = temp->right;}root->left = reverse(cur);}}root = root->right;}TreeNode* cur = reverse(head);TreeNode* temp = cur;while(temp!=nullptr){res.push_back(temp->val);temp = temp->right;}root = reverse(cur);return res;}
};

如果一个方法需要第三次信息的强整合（向左树要信息，向右树要信息再处理），必须用递归；如果不需要，则morris遍历是最优解