Skip to content

Latest commit

 

History

History
382 lines (320 loc) · 10.9 KB

基础提升05.md

File metadata and controls

382 lines (320 loc) · 10.9 KB
Raw

5. 树形dp套路、Morris遍历

MyTreeDP.cpp

5.1 树形dp套路

树形dp套路使用前提：

  • 如果题目求解目标是S规则，则求解流程可以定成以每一个节点为头节点的子树在s规则下的每一个答案，并且最终答案一定在其中。

第一步：

  • 以某个节点X为头节点的子树中，分析答案有哪些可能性，并且这种分析是以X的左子树、X的右子树和X整棵树的角度来考虑可能性的

第二步：

  • 根据第一步的可能性分析，列出所有需要的信息

第三步：

  • 合并第二步的信息，对左树和右树提出同样的要求，并写出信息结构

第四步：

  • 设计递归函数，递归函数是处理以X为头节点的情况下的答案。

  • 包括设计递归的basecase，默认直接得到左树和右树的所有信息，以及把可能性做整合，并且要返回第三步的信息结构

1. 二叉树节点间的最大距离问题

从二叉树的节点a出发，可以向上或者向下走，但沿途的节点只能经过一次，到达节点b时路径上的节点个数叫作a到b的距离，那么二叉树任何两个节点之间都有距离，求整棵树上的最大距离。

分析：

假设 x 节点为头节点，

(1) x 不参与

最大距离可能为：

  • 左树上的最大距离
  • 右树上的最大距离

(2) x 参与

最大距离可能为：

  • 左树上最远节点 -> X -> 右树上最远节点 (左树的高 + 1 + 右树上的高)

因此可以确定返回值结构为：{最大距离，高}，在所有情况中求一个最大值。

✅tested

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), righ(right）{}
 };

class Info {
public:
    Info(int dis, int h) : maxDistance(dis), height(h) {}
    int maxDistance;
    int height;
};
Info process(TreeNode* root){
    if(root == nullptr){
        return Info(0,0);
    }
    Info leftInfo = process(root->left);
    Info rightInfo = process(root->right);
    // Info
    int p1 = leftInfo.maxDistance;
    int p2 = rightInfo.maxDistance;
    int p3 = leftInfo.height + rightInfo.height + 1;
    int maxDistance = max(p3, max(p1, p2));
    int height = max(leftInfo.height, rightInfo.height) + 1;
    return Info(maxDistance, height);
}
int diameterOfBinaryTree(TreeNode* root) {
    if(root == nullptr){
        return 0;
    }
    return process(root).maxDistance - 1;
}

2. 派对的最大快乐值

员工信息的定义如下：

class TreeNode{
public:
    TreeNode(int h) : happy(h) { }
    
    int happy;                  //这名员工可以带来的快乐值 
    vector<TreeNode*> nexts;    //这名员工有哪些直接下级
};

公司的每个员工都符合Employee类的描述。

整个公司的人员结构可以看作是一棵标准的、没有环的多叉树，树的头节点是公司唯一的老板。除老板之外的每个员工都有唯一的直接上级。

叶节点是没有任何下属的基层员工（subordinates列表为空），除基层员工外，每个员工都有一个或多个直接下级。

这个公司现在要办party，你可以决定哪些员工来，哪些员工不来。但是要遵循如下规则:

  1. 如果某个员工来了，那么这个员工的所有直接下级都不能来
  2. 派对的整体快乐值是所有到场员工快乐值的累加
  3. 你的目标是让派对的整体快乐值尽量大

给定一棵多叉树的头节点boss，请返回派对的最大快乐值。

✅tested

class Info{
public:
    Info(int come, int nocome) : comeMaxhappy(come), nocomeMaxhappy(nocome) { }

    int comeMaxhappy;
    int nocomeMaxhappy;
};
Info* process(TreeNode* root){
    if(root->nexts.empty()){
        return new Info(root->happy, 0);
    }
    int come = root->happy; // x 来的情况下，整棵树最大收益
    int nocome = 0;         // x 不来的情况下，整棵树最大收益
    for(TreeNode* next : root->nexts){
        Info* nextInfo = process(next);
        come += nextInfo->nocomeMaxhappy;   // 所有直接下级都不来
        nocome += max(nextInfo->comeMaxhappy, nextInfo->nocomeMaxhappy);    // 直接下级可以来也可以不来
    }
    return new Info(come, nocome);
}
int main()
{
    int n, root;
    cin >> n >> root;
    vector<TreeNode*> happy(n);
    for(int i = 0; i < n; i++){
        int t;
        cin >> t;
        happy[i] = new TreeNode(t);
    }
    for(int i = 0; i < n - 1; i++){
        int ui, vi;
        cin >> ui >> vi;
        happy[ui - 1]->nexts.push_back(happy[vi - 1]);
    }
    Info* res = process(happy[root - 1]);
    cout << max(res->comeMaxhappy, res->nocomeMaxhappy) << endl;
}

5.2 Morris 遍历

一种遍历二叉树的方式，并且时间复杂度O(N)，额外空间复杂度O(1)，通过利用原树中大量空闲指针的方式，达到节省空间的目的

  • 面试用，笔试不推荐

1. Morris遍历细节

假设来到当前节点cur，开始时cur来到头节点位置

  1. 如果cur没有左孩子，cur向右移动（cur = cur.right）

  2. 如果cur有左孩子，找到左子树上最右的节点mostRight：

    a. 如果mostRight的右指针指向空，让其指向cur，然后cur向左移动(cur = cur.left)

    b. 如果mostRight的右指针指向cur，让其指向null，然后cur向右移动(cur = cur.right)

  3. cur为空时遍历停止

总结：

  • 一个节点如果有左树，一定能回到它两次
  • 没有左树的节点，只能回到它一次
void morris(Node* head) {
    if (head == nullptr) {
        return;
    }
    Node* cur = head;
    Node* mostRight = nullptr;
    while (cur) {
        mostRight = cur->left;
        if (mostRight != nullptr) {    // 如果有左子树
            while (mostRight->right && mostRight->right != cur) {
                mostRight = mostRight->right;
            }
            // mostRight 变成了cur左子树上的最右节点
            if (mostRight->right == nullptr) {
                mostRight->right = cur;
                cur = cur->left;
                continue;
            }
            else {  // mostRight == cur
                mostRight->right = nullptr;
            }
        }
        cur = cur->right;
    }
}

2. 先序遍历

  • 如果一个节点只到达一次，直接打印
  • 如果可以到达两次，第一次打印
void morrisPre(Node* head) {
    if (head == nullptr) {
        return;
    }
    Node* cur = head;
    Node* mostRight = nullptr;
    while (cur) {
        mostRight = cur->left;
        if (mostRight != nullptr) {    // 如果有左子树
            while (mostRight->right && mostRight->right != cur) {
                mostRight = mostRight->right;
            }
            // mostRight 变成了cur左子树上的最右节点
            if (mostRight->right == nullptr) {
                cout << cur->value << endl;
                mostRight->right = cur;
                cur = cur->left;
                continue;
            }
            else {  // mostRight == cur
                mostRight->right = nullptr;
            }
        }
        else{
            cout << cur->value << endl;
        }
        cur = cur->right;
    }
}

3. 中序遍历

void morrisIn(Node* head) {
    if (head == nullptr) {
        return;
    }
    Node* cur = head;
    Node* mostRight = nullptr;
    while (cur) {
        mostRight = cur->left;
        if (mostRight != nullptr) {    // 如果有左子树
            while (mostRight->right && mostRight->right != cur) {
                mostRight = mostRight->right;
            }
            // mostRight 变成了cur左子树上的最右节点
            if (mostRight->right == nullptr) {
                mostRight->right = cur;
                cur = cur->left;
                continue;
            }
            else {  // mostRight == cur
                mostRight->right = nullptr;
            }
        }
        cout << cur->value << endl;
        cur = cur->right;
    }
}

4. 后序遍历

  • 如果可以到达两次，第二次时，逆序打印自己左树的右边界
  • 最后，逆序打印整棵树的右边界
// 反转链表
Node* reverseEdge(Node* from){
    Node* pre = nullptr;
    Node* next = nullptr;
    while(from){
        next = from->right;
        from->right = pre;
        pre = from;
        from = next;
    }
    return pre;
}
// 以 x 为头的树，逆序打印这棵树的右边界
void printEdge(Node* x){
    Node* tail = reverseEdge(x);
    Node* cur = tail;
    while(cur){
        cout << cur->value << " " << endl;
        cur = cur->right;
    }
    reverseEdge(x);
}
void morrisPos(Node* head) {
    if (head == nullptr) {
        return;
    }
    Node* cur = head;
    Node* mostRight = nullptr;
    while (cur) {
        mostRight = cur->left;
        if (mostRight != nullptr) {    // 如果有左子树
            while (mostRight->right && mostRight->right != cur) {
                mostRight = mostRight->right;
            }
            // mostRight 变成了cur左子树上的最右节点
            if (mostRight->right == nullptr) {
                mostRight->right = cur;
                cur = cur->left;
                continue;
            }
            else {  // mostRight == cur
                mostRight->right = nullptr;
                printEdge(cur->left);
            }
        }
        cur = cur->right;
    }
    printEdge(head);
    cout << endl;
}

5. 搜索二叉树

判断一棵树是否是搜索二叉树

bool isBST(Node* head) {
    if (head == nullptr) {
        return true;
    }
    Node* cur = head;
    Node* mostRight = nullptr;
    int preValue = INTMAX_MIN;
    while (cur) {
        mostRight = cur->left;
        if (mostRight != nullptr) {    // 如果有左子树
            while (mostRight->right && mostRight->right != cur) {
                mostRight = mostRight->right;
            }
            // mostRight 变成了cur左子树上的最右节点
            if (mostRight->right == nullptr) {
                mostRight->right = cur;
                cur = cur->left;
                continue;
            }
            else {  // mostRight == cur
                mostRight->right = nullptr;
            }
        }
        if(cur->value <= preValue){
            return false;
        }
        preValue = cur->value;
        cur = cur->right;
    }
    return true;
}