程序员经验分享-hwhale

【LeetCode刷题日记】树类题目常见题型

2023-05-16

文章目录

    • 树基础知识
    • [104. 二叉树的最大深度](https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/)
    • [102. 二叉树的层序遍历](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/)
    • [94. 二叉树的中序遍历](https://leetcode-cn.com/problems/binary-tree-inorder-traversal/)
    • [101. 对称二叉树](https://leetcode-cn.com/problems/symmetric-tree/)
    • [98. 验证二叉搜索树](https://leetcode-cn.com/problems/validate-binary-search-tree/)
    • [100. 相同的树](https://leetcode-cn.com/problems/same-tree/)
    • [226. 翻转二叉树](https://leetcode-cn.com/problems/invert-binary-tree/)
    • [144. 二叉树的前序遍历](https://leetcode-cn.com/problems/binary-tree-preorder-traversal/)
    • [111. 二叉树的最小深度](https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/)
    • [112. 路径总和](https://leetcode-cn.com/problems/path-sum/)
    • [145. 二叉树的后序遍历](https://leetcode-cn.com/problems/binary-tree-postorder-traversal/)
    • [110. 平衡二叉树](https://leetcode-cn.com/problems/balanced-binary-tree/)
    • [114. 二叉树展开为链表](https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/)

树基础知识

https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906222158308.png

https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906222223764.png

https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906222239733.png

在这里插入图片描述

https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906222307539.png

https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906222321406.png

在这里插入图片描述

在这里插入图片描述

https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906222403335.png

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

下面用图解来说明一下前序遍历算法的递归过程。

在这里插入图片描述
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-t649bQ1H-1631410485856)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906222707569.png#pic_center)]
)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WJP8QBir-1631410165737)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906223024841.png

104. 二叉树的最大深度

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hokROzkn-1631410165737)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906225439631.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-c6vkvJPE-1631410165738)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906230105322.png)]

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int maxDepth(struct TreeNode *root) {
    if (root == NULL) return 0;
    return fmax(maxDepth(root->left), maxDepth(root->right)) + 1;
}

-------------------------------------------------------------------

/**
 * 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 Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-K6grKsYv-1631410165738)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906230159673.png)]

struct QueNode {
    struct TreeNode *p;
    struct QueNode *next;
};

void init(struct QueNode **p, struct TreeNode *t) {
    (*p) = (struct QueNode *)malloc(sizeof(struct QueNode));
    (*p)->p = t;
    (*p)->next = NULL;
}

int maxDepth(struct TreeNode *root) {
    if (root == NULL) return 0;
    struct QueNode *left, *right;
    init(&left, root);
    right = left;
    int ans = 0, sz = 1, tmp = 0;
    while (left != NULL) {
        tmp = 0;
        while (sz > 0) {
            if (left->p->left != NULL) {
                init(&right->next, left->p->left);
                right = right->next;
                tmp++;
            }
            if (left->p->right != NULL) {
                init(&right->next, left->p->right);
                right = right->next;
                tmp++;
            }
            left = left->next;
            sz--;
        }
        sz += tmp;
        ans++;
    }
    return ans;
}

---------------------------------------------------------------------
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        queue<TreeNode*> Q;
        Q.push(root);
        int ans = 0;
        while (!Q.empty()) {
            int sz = Q.size();
            while (sz > 0) {
                TreeNode* node = Q.front();Q.pop();
                if (node->left) Q.push(node->left);
                if (node->right) Q.push(node->right);
                sz -= 1;
            }
            ans += 1;
        } 
        return ans;
    }
};

102. 二叉树的层序遍历

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FSQWBJz6-1631410165739)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906230630256.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hVrPvVav-1631410165739)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906230809581.png)]

/**
 * 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 Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector <vector <int>> ret;
        if (!root) {
            return ret;
        }

        queue <TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int currentLevelSize = q.size();
            ret.push_back(vector <int> ());
            for (int i = 1; i <= currentLevelSize; ++i) {
                auto node = q.front(); q.pop();
                ret.back().push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        
        return ret;
    }
};

94. 二叉树的中序遍历

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-haY1LbiS-1631410165739)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906231012868.png)]

image-20210906231031428

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-eKamUhz6-1631410165740)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906231108467.png)]

void inorder(struct TreeNode* root, int* res, int* resSize) {
    if (!root) {
        return;
    }
    inorder(root->left, res, resSize);
    res[(*resSize)++] = root->val;
    inorder(root->right, res, resSize);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int* res = malloc(sizeof(int) * 501);
    *returnSize = 0;
    inorder(root, res, returnSize);
    return res;
}

---------------------------------------------------------------------
class Solution {
public:
    void inorder(TreeNode* root, vector<int>& res) {
        if (!root) {
            return;
        }
        inorder(root->left, res);
        res.push_back(root->val);
        inorder(root->right, res);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        inorder(root, res);
        return res;
    }
};

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1ykLuVUp-1631410165741)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906231203588.png)]

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = 0;
    int* res = malloc(sizeof(int) * 501);
    struct TreeNode** stk = malloc(sizeof(struct TreeNode*) * 501);
    int top = 0;
    while (root != NULL || top > 0) {
        while (root != NULL) {
            stk[top++] = root;
            root = root->left;
        }
        root = stk[--top];
        res[(*returnSize)++] = root->val;
        root = root->right;
    }
    return res;
}

---------------------------------------------------------------
Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        while (root != nullptr || !stk.empty()) {
            while (root != nullptr) {
                stk.push(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
            res.push_back(root->val);
            root = root->right;
        }
        return res;
    }
};

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dOsyM3uB-1631410165741)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906231316031.png)]

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int* res = malloc(sizeof(int) * 501);
    *returnSize = 0;
    struct TreeNode* predecessor = NULL;

    while (root != NULL) {
        if (root->left != NULL) {
            // predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
            predecessor = root->left;
            while (predecessor->right != NULL && predecessor->right != root) {
                predecessor = predecessor->right;
            }

            // 让 predecessor 的右指针指向 root，继续遍历左子树
            if (predecessor->right == NULL) {
                predecessor->right = root;
                root = root->left;
            }
            // 说明左子树已经访问完了，我们需要断开链接
            else {
                res[(*returnSize)++] = root->val;
                predecessor->right = NULL;
                root = root->right;
            }
        }
        // 如果没有左孩子，则直接访问右孩子
        else {
            res[(*returnSize)++] = root->val;
            root = root->right;
        }
    }
    return res;
}

-----------------------------------------------------------------
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        TreeNode *predecessor = nullptr;

        while (root != nullptr) {
            if (root->left != nullptr) {
                // predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
                predecessor = root->left;
                while (predecessor->right != nullptr && predecessor->right != root) {
                    predecessor = predecessor->right;
                }
                
                // 让 predecessor 的右指针指向 root，继续遍历左子树
                if (predecessor->right == nullptr) {
                    predecessor->right = root;
                    root = root->left;
                }
                // 说明左子树已经访问完了，我们需要断开链接
                else {
                    res.push_back(root->val);
                    predecessor->right = nullptr;
                    root = root->right;
                }
            }
            // 如果没有左孩子，则直接访问右孩子
            else {
                res.push_back(root->val);
                root = root->right;
            }
        }
        return res;
    }
};

101. 对称二叉树

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DDaijCXA-1631410165741)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906231723650.png)]

image-20210906231758325

class Solution {
public:
    bool check(TreeNode *p, TreeNode *q) {
        if (!p && !q) return true;
        if (!p || !q) return false;
        return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
    }

    bool isSymmetric(TreeNode* root) {
        return check(root, root);
    }
};

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TJOn4n2k-1631410165742)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906231838027.png)]

class Solution {
public:
    bool check(TreeNode *u, TreeNode *v) {
        queue <TreeNode*> q;
        q.push(u); q.push(v);
        while (!q.empty()) {
            u = q.front(); q.pop();
            v = q.front(); q.pop();
            if (!u && !v) continue;
            if ((!u || !v) || (u->val != v->val)) return false;

            q.push(u->left); 
            q.push(v->right);

            q.push(u->right); 
            q.push(v->left);
        }
        return true;
    }

    bool isSymmetric(TreeNode* root) {
        return check(root, root);
    }
};

98. 验证二叉搜索树

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XEZkgoUx-1631410165742)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906232046142.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VP8vQGV3-1631410165743)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906232733702.png)]

class Solution {
public:
    bool helper(TreeNode* root, long long lower, long long upper) {
        if (root == nullptr) {
            return true;
        }
        if (root -> val <= lower || root -> val >= upper) {
            return false;
        }
        return helper(root -> left, lower, root -> val) && helper(root -> right, root -> val, upper);
    }
    bool isValidBST(TreeNode* root) {
        return helper(root, LONG_MIN, LONG_MAX);
    }
};

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YXztDcbC-1631410165743)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906232758657.png)]

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> stack;
        long long inorder = (long long)INT_MIN - 1;

        while (!stack.empty() || root != nullptr) {
            while (root != nullptr) {
                stack.push(root);
                root = root -> left;
            }
            root = stack.top();
            stack.pop();
            // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
            if (root -> val <= inorder) {
                return false;
            }
            inorder = root -> val;
            root = root -> right;
        }
        return true;
    }
};

100. 相同的树

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9x97yxnb-1631410165743)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906232905376.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tpraHkvi-1631410165744)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906232942970.png)]

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if (p == NULL && q == NULL) {
        return true;
    } else if (p == NULL || q == NULL) {
        return false;
    } else if (p->val != q->val) {
        return false;
    } else {
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
}

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr) {
            return true;
        } else if (p == nullptr || q == nullptr) {
            return false;
        } else if (p->val != q->val) {
            return false;
        } else {
            return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
        }
    }
};

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7oaAoo5M-1631410165744)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906233029546.png)]

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if (p == NULL && q == NULL) {
        return true;
    } else if (p == NULL || q == NULL) {
        return false;
    }
    struct TreeNode** que1 = (struct TreeNode**)malloc(sizeof(struct TreeNode*));
    struct TreeNode** que2 = (struct TreeNode**)malloc(sizeof(struct TreeNode*));
    int queleft1 = 0, queright1 = 0;
    int queleft2 = 0, queright2 = 0;
    que1[queright1++] = p;
    que2[queright2++] = q;
    while (queleft1 < queright1 && queleft2 < queright2) {
        struct TreeNode* node1 = que1[queleft1++];
        struct TreeNode* node2 = que2[queleft2++];
        if (node1->val != node2->val) {
            return false;
        }
        struct TreeNode* left1 = node1->left;
        struct TreeNode* right1 = node1->right;
        struct TreeNode* left2 = node2->left;
        struct TreeNode* right2 = node2->right;
        if ((left1 == NULL) ^ (left2 == NULL)) {
            return false;
        }
        if ((right1 == NULL) ^ (right2 == NULL)) {
            return false;
        }
        if (left1 != NULL) {
            queright1++;
            que1 = realloc(que1, sizeof(struct TreeNode*) * queright1);
            que1[queright1 - 1] = left1;
        }
        if (right1 != NULL) {
            queright1++;
            que1 = realloc(que1, sizeof(struct TreeNode*) * queright1);
            que1[queright1 - 1] = right1;
        }
        if (left2 != NULL) {
            queright2++;
            que2 = realloc(que2, sizeof(struct TreeNode*) * queright2);
            que2[queright2 - 1] = left2;
        }
        if (right2 != NULL) {
            queright2++;
            que2 = realloc(que2, sizeof(struct TreeNode*) * queright2);
            que2[queright2 - 1] = right2;
        }
    }
    return queleft1 == queright1 && queleft2 == queright2;
}

--------------------------------------------------------------------
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr) {
            return true;
        } else if (p == nullptr || q == nullptr) {
            return false;
        }
        queue <TreeNode*> queue1, queue2;
        queue1.push(p);
        queue2.push(q);
        while (!queue1.empty() && !queue2.empty()) {
            auto node1 = queue1.front();
            queue1.pop();
            auto node2 = queue2.front();
            queue2.pop();
            if (node1->val != node2->val) {
                return false;
            }
            auto left1 = node1->left, right1 = node1->right, left2 = node2->left, right2 = node2->right;
            if ((left1 == nullptr) ^ (left2 == nullptr)) {
                return false;
            }
            if ((right1 == nullptr) ^ (right2 == nullptr)) {
                return false;
            }
            if (left1 != nullptr) {
                queue1.push(left1);
            }
            if (right1 != nullptr) {
                queue1.push(right1);
            }
            if (left2 != nullptr) {
                queue2.push(left2);
            }
            if (right2 != nullptr) {
                queue2.push(right2);
            }
        }
        return queue1.empty() && queue2.empty();
    }
};

226. 翻转二叉树

image-20210906233146066

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-eHkkuHEY-1631410165745)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906233211449.png)]

struct TreeNode* invertTree(struct TreeNode* root) {
    if (root == NULL) {
        return NULL;
    }
    struct TreeNode* left = invertTree(root->left);
    struct TreeNode* right = invertTree(root->right);
    root->left = right;
    root->right = left;
    return root;
}

--------------------------------------------------------
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }
        TreeNode* left = invertTree(root->left);
        TreeNode* right = invertTree(root->right);
        root->left = right;
        root->right = left;
        return root;
    }
};

144. 二叉树的前序遍历

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IVY2Xsww-1631410165745)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906233405175.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VqSyQqMO-1631410165746)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906233442557.png)]

void preorder(struct TreeNode* root, int* res, int* resSize) {
    if (root == NULL) {
        return;
    }
    res[(*resSize)++] = root->val;
    preorder(root->left, res, resSize);
    preorder(root->right, res, resSize);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int* res = malloc(sizeof(int) * 2000);
    *returnSize = 0;
    preorder(root, res, returnSize);
    return res;
}

------------------------------------------------------------------
class Solution {
public:
    void preorder(TreeNode *root, vector<int> &res) {
        if (root == nullptr) {
            return;
        }
        res.push_back(root->val);
        preorder(root->left, res);
        preorder(root->right, res);
    }

    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> res;
        preorder(root, res);
        return res;
    }
};

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4Ui2W7OE-1631410165746)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906233539153.png)]

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int* res = malloc(sizeof(int) * 2000);
    *returnSize = 0;
    if (root == NULL) {
        return res;
    }

    struct TreeNode* stk[2000];
    struct TreeNode* node = root;
    int stk_top = 0;
    while (stk_top > 0 || node != NULL) {
        while (node != NULL) {
            res[(*returnSize)++] = node->val;
            stk[stk_top++] = node;
            node = node->left;
        }
        node = stk[--stk_top];
        node = node->right;
    }
    return res;
}

----------------------------------------------------------------------
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }

        stack<TreeNode*> stk;
        TreeNode* node = root;
        while (!stk.empty() || node != nullptr) {
            while (node != nullptr) {
                res.emplace_back(node->val);
                stk.emplace(node);
                node = node->left;
            }
            node = stk.top();
            stk.pop();
            node = node->right;
        }
        return res;
    }
};

111. 二叉树的最小深度

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ccT0q5XO-1631410165747)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906233645598.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-x0EskIlp-1631410165747)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906233711706.png)]

int minDepth(struct TreeNode *root) {
    if (root == NULL) {
        return 0;
    }

    if (root->left == NULL && root->right == NULL) {
        return 1;
    }

    int min_depth = INT_MAX;
    if (root->left != NULL) {
        min_depth = fmin(minDepth(root->left), min_depth);
    }
    if (root->right != NULL) {
        min_depth = fmin(minDepth(root->right), min_depth);
    }

    return min_depth + 1;
}

------------------------------------------------------------------------
class Solution {
public:
    int minDepth(TreeNode *root) {
        if (root == nullptr) {
            return 0;
        }

        if (root->left == nullptr && root->right == nullptr) {
            return 1;
        }

        int min_depth = INT_MAX;
        if (root->left != nullptr) {
            min_depth = min(minDepth(root->left), min_depth);
        }
        if (root->right != nullptr) {
            min_depth = min(minDepth(root->right), min_depth);
        }

        return min_depth + 1;
    }
};

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ydP328lE-1631410165748)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906233802403.png)]

typedef struct {
    int val;
    struct TreeNode *node;
    struct queNode *next;
} queNode;

void init(queNode **p, int val, struct TreeNode *node) {
    (*p) = (queNode *)malloc(sizeof(queNode));
    (*p)->val = val;
    (*p)->node = node;
    (*p)->next = NULL;
}

int minDepth(struct TreeNode *root) {
    if (root == NULL) {
        return 0;
    }

    queNode *queLeft, *queRight;
    init(&queLeft, 1, root);
    queRight = queLeft;
    while (queLeft != NULL) {
        struct TreeNode *node = queLeft->node;
        int depth = queLeft->val;
        if (node->left == NULL && node->right == NULL) {
            return depth;
        }
        if (node->left != NULL) {
            init(&queRight->next, depth + 1, node->left);
            queRight = queRight->next;
        }
        if (node->right != NULL) {
            init(&queRight->next, depth + 1, node->right);
            queRight = queRight->next;
        }
        queLeft = queLeft->next;
    }
    return false;
}

-------------------------------------------------------------------------
class Solution {
public:
    int minDepth(TreeNode *root) {
        if (root == nullptr) {
            return 0;
        }

        queue<pair<TreeNode *, int> > que;
        que.emplace(root, 1);
        while (!que.empty()) {
            TreeNode *node = que.front().first;
            int depth = que.front().second;
            que.pop();
            if (node->left == nullptr && node->right == nullptr) {
                return depth;
            }
            if (node->left != nullptr) {
                que.emplace(node->left, depth + 1);
            }
            if (node->right != nullptr) {
                que.emplace(node->right, depth + 1);
            }
        }

        return 0;
    }
};

112. 路径总和

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-00hgieFP-1631410165748)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906233938807.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-H8hDaV3s-1631410165748)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906234012608.png)]

typedef struct queNode {
    int val;
    struct TreeNode *node;
    struct queNode *next;
} queNode;

void init(struct queNode **p, int val, struct TreeNode *node) {
    (*p) = (struct queNode *)malloc(sizeof(struct queNode));
    (*p)->val = val;
    (*p)->node = node;
    (*p)->next = NULL;
}

bool hasPathSum(struct TreeNode *root, int sum) {
    if (root == NULL) {
        return false;
    }
    struct queNode *queLeft, *queRight;
    init(&queLeft, root->val, root);
    queRight = queLeft;
    while (queLeft != NULL) {
        struct TreeNode *now = queLeft->node;
        int temp = queLeft->val;
        if (now->left == NULL && now->right == NULL) {
            if (temp == sum) return true;
        }
        if (now->left != NULL) {
            init(&queRight->next, now->left->val + temp, now->left);
            queRight = queRight->next;
        }
        if (now->right != NULL) {
            init(&queRight->next, now->right->val + temp, now->right);
            queRight = queRight->next;
        }
        queLeft = queLeft->next;
    }
    return false;
}

---------------------------------------------------------------------------
class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (root == nullptr) {
            return false;
        }
        queue<TreeNode *> que_node;
        queue<int> que_val;
        que_node.push(root);
        que_val.push(root->val);
        while (!que_node.empty()) {
            TreeNode *now = que_node.front();
            int temp = que_val.front();
            que_node.pop();
            que_val.pop();
            if (now->left == nullptr && now->right == nullptr) {
                if (temp == sum) {
                    return true;
                }
                continue;
            }
            if (now->left != nullptr) {
                que_node.push(now->left);
                que_val.push(now->left->val + temp);
            }
            if (now->right != nullptr) {
                que_node.push(now->right);
                que_val.push(now->right->val + temp);
            }
        }
        return false;
    }
};

145. 二叉树的后序遍历

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SEiyjvXK-1631410165749)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906234156320.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EAUHEPx9-1631410165749)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906234226463.png)]

void postorder(struct TreeNode *root, int *res, int *resSize) {
    if (root == NULL) {
        return;
    }
    postorder(root->left, res, resSize);
    postorder(root->right, res, resSize);
    res[(*resSize)++] = root->val;
}

int *postorderTraversal(struct TreeNode *root, int *returnSize) {
    int *res = malloc(sizeof(int) * 2001);
    *returnSize = 0;
    postorder(root, res, returnSize);
    return res;
}

--------------------------------------------------------------------
class Solution {
public:
    void postorder(TreeNode *root, vector<int> &res) {
        if (root == nullptr) {
            return;
        }
        postorder(root->left, res);
        postorder(root->right, res);
        res.push_back(root->val);
    }

    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> res;
        postorder(root, res);
        return res;
    }
};

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tHyQn7hP-1631410165750)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906234322640.png)]

int *postorderTraversal(struct TreeNode *root, int *returnSize) {
    int *res = malloc(sizeof(int) * 2001);
    *returnSize = 0;
    if (root == NULL) {
        return res;
    }
    struct TreeNode **stk = malloc(sizeof(struct TreeNode *) * 2001);
    int top = 0;
    struct TreeNode *prev = NULL;
    while (root != NULL || top > 0) {
        while (root != NULL) {
            stk[top++] = root;
            root = root->left;
        }
        root = stk[--top];
        if (root->right == NULL || root->right == prev) {
            res[(*returnSize)++] = root->val;
            prev = root;
            root = NULL;
        } else {
            stk[top++] = root;
            root = root->right;
        }
    }
    return res;
}

-----------------------------------------------------------------------
class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }

        stack<TreeNode *> stk;
        TreeNode *prev = nullptr;
        while (root != nullptr || !stk.empty()) {
            while (root != nullptr) {
                stk.emplace(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
            if (root->right == nullptr || root->right == prev) {
                res.emplace_back(root->val);
                prev = root;
                root = nullptr;
            } else {
                stk.emplace(root);
                root = root->right;
            }
        }
        return res;
    }
};

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XExe5TJK-1631410165750)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906234403833.png)]

void addPath(int *vec, int *vecSize, struct TreeNode *node) {
    int count = 0;
    while (node != NULL) {
        ++count;
        vec[(*vecSize)++] = node->val;
        node = node->right;
    }
    for (int i = (*vecSize) - count, j = (*vecSize) - 1; i < j; ++i, --j) {
        int t = vec[i];
        vec[i] = vec[j];
        vec[j] = t;
    }
}

int *postorderTraversal(struct TreeNode *root, int *returnSize) {
    int *res = malloc(sizeof(int) * 2001);
    *returnSize = 0;
    if (root == NULL) {
        return res;
    }

    struct TreeNode *p1 = root, *p2 = NULL;

    while (p1 != NULL) {
        p2 = p1->left;
        if (p2 != NULL) {
            while (p2->right != NULL && p2->right != p1) {
                p2 = p2->right;
            }
            if (p2->right == NULL) {
                p2->right = p1;
                p1 = p1->left;
                continue;
            } else {
                p2->right = NULL;
                addPath(res, returnSize, p1->left);
            }
        }
        p1 = p1->right;
    }
    addPath(res, returnSize, root);
    return res;
}

--------------------------------------------------------------------------
class Solution {
public:
    void addPath(vector<int> &vec, TreeNode *node) {
        int count = 0;
        while (node != nullptr) {
            ++count;
            vec.emplace_back(node->val);
            node = node->right;
        }
        reverse(vec.end() - count, vec.end());
    }

    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }

        TreeNode *p1 = root, *p2 = nullptr;

        while (p1 != nullptr) {
            p2 = p1->left;
            if (p2 != nullptr) {
                while (p2->right != nullptr && p2->right != p1) {
                    p2 = p2->right;
                }
                if (p2->right == nullptr) {
                    p2->right = p1;
                    p1 = p1->left;
                    continue;
                } else {
                    p2->right = nullptr;
                    addPath(res, p1->left);
                }
            }
            p1 = p1->right;
        }
        addPath(res, root);
        return res;
    }
};

110. 平衡二叉树

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5Ck6xuXv-1631410165751)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906234611310.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-efecf3g3-1631410165751)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906234654446.png)]

int height(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    } else {
        return fmax(height(root->left), height(root->right)) + 1;
    }
}

bool isBalanced(struct TreeNode* root) {
    if (root == NULL) {
        return true;
    } else {
        return fabs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
    }
}

------------------------------------------------------------------------
class Solution {
public:
    int height(TreeNode* root) {
        if (root == NULL) {
            return 0;
        } else {
            return max(height(root->left), height(root->right)) + 1;
        }
    }

    bool isBalanced(TreeNode* root) {
        if (root == NULL) {
            return true;
        } else {
            return abs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
        }
    }
};

image-20210906234744881

int height(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    if (leftHeight == -1 || rightHeight == -1 || fabs(leftHeight - rightHeight) > 1) {
        return -1;
    } else {
        return fmax(leftHeight, rightHeight) + 1;
    }
}

bool isBalanced(struct TreeNode* root) {
    return height(root) >= 0;
}

---------------------------------------------------------------------
class Solution {
public:
    int height(TreeNode* root) {
        if (root == NULL) {
            return 0;
        }
        int leftHeight = height(root->left);
        int rightHeight = height(root->right);
        if (leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return max(leftHeight, rightHeight) + 1;
        }
    }

    bool isBalanced(TreeNode* root) {
        return height(root) >= 0;
    }
};

114. 二叉树展开为链表

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7hIa3TA8-1631410165752)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906235203849.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AQjmOXnn-1631410165752)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906235425413.png)]

int num;

void flatten(struct TreeNode* root) {
    num = 0;
    struct TreeNode** l = (struct TreeNode**)malloc(0);
    preorderTraversal(root, &l);
    for (int i = 1; i < num; i++) {
        struct TreeNode *prev = l[i - 1], *curr = l[i];
        prev->left = NULL;
        prev->right = curr;
    }
    free(l);
}

void preorderTraversal(struct TreeNode* root, struct TreeNode*** l) {
    if (root != NULL) {
        num++;
        (*l) = (struct TreeNode**)realloc((*l), sizeof(struct TreeNode*) * num);
        (*l)[num - 1] = root;
        preorderTraversal(root->left, l);
        preorderTraversal(root->right, l);
    }
}

------------------------------------------------------------------------
class Solution {
public:
    void flatten(TreeNode* root) {
        vector<TreeNode*> l;
        preorderTraversal(root, l);
        int n = l.size();
        for (int i = 1; i < n; i++) {
            TreeNode *prev = l.at(i - 1), *curr = l.at(i);
            prev->left = nullptr;
            prev->right = curr;
        }
    }

    void preorderTraversal(TreeNode* root, vector<TreeNode*> &l) {
        if (root != NULL) {
            l.push_back(root);
            preorderTraversal(root->left, l);
            preorderTraversal(root->right, l);
        }
    }
};

void flatten(struct TreeNode* root) {
    struct TreeNode** stk = (struct TreeNode**)malloc(0);
    int stk_top = 0;
    struct TreeNode** vec = (struct TreeNode**)malloc(0);
    int vec_len = 0;
    struct TreeNode* node = root;
    while (node != NULL || stk_top != 0) {
        while (node != NULL) {
            vec_len++;
            vec = (struct TreeNode**)realloc(vec, sizeof(struct TreeNode*) * vec_len);
            vec[vec_len - 1] = node;
            stk_top++;
            stk = (struct TreeNode**)realloc(stk, sizeof(struct TreeNode*) * stk_top);
            stk[stk_top - 1] = node;
            node = node->left;
        }
        node = stk[--stk_top];
        node = node->right;
    }
    for (int i = 1; i < vec_len; i++) {
        struct TreeNode *prev = vec[i - 1], *curr = vec[i];
        prev->left = NULL;
        prev->right = curr;
    }
    free(stk);
    free(vec);
}

class Solution {
public:
    void flatten(TreeNode* root) {
        auto v = vector<TreeNode*>();
        auto stk = stack<TreeNode*>();
        TreeNode *node = root;
        while (node != nullptr || !stk.empty()) {
            while (node != nullptr) {
                v.push_back(node);
                stk.push(node);
                node = node->left;
            }
            node = stk.top(); stk.pop();
            node = node->right;
        }
        int size = v.size();
        for (int i = 1; i < size; i++) {
            auto prev = v.at(i - 1), curr = v.at(i);
            prev->left = nullptr;
            prev->right = curr;
        }
    }
};

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-s1hNkuMD-1631410165752)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906235425413.png)]

void flatten(struct TreeNode *root) {
    if (root == NULL) {
        return;
    }
    struct TreeNode **stk = (struct TreeNode **)malloc(sizeof(struct TreeNode *));
    int stk_top = 1;
    stk[0] = root;
    struct TreeNode *prev = NULL;
    while (stk_top != 0) {
        struct TreeNode *curr = stk[--stk_top];
        if (prev != NULL) {
            prev->left = NULL;
            prev->right = curr;
        }
        struct TreeNode *left = curr->left, *right = curr->right;
        if (right != NULL) {
            stk_top++;
            stk = (struct TreeNode **)realloc(stk, sizeof(struct TreeNode *) * stk_top);
            stk[stk_top - 1] = right;
        }
        if (left != NULL) {
            stk_top++;
            stk = (struct TreeNode **)realloc(stk, sizeof(struct TreeNode *) * stk_top);
            stk[stk_top - 1] = left;
        }
        prev = curr;
    }
    free(stk);
}

--------------------------------------------------------------------
class Solution {
public:
    void flatten(TreeNode* root) {
        if (root == nullptr) {
            return;
        }
        auto stk = stack<TreeNode*>();
        stk.push(root);
        TreeNode *prev = nullptr;
        while (!stk.empty()) {
            TreeNode *curr = stk.top(); stk.pop();
            if (prev != nullptr) {
                prev->left = nullptr;
                prev->right = curr;
            }
            TreeNode *left = curr->left, *right = curr->right;
            if (right != nullptr) {
                stk.push(right);
            }
            if (left != nullptr) {
                stk.push(left);
            }
            prev = curr;
        }
    }
};
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

【LeetCode刷题日记】树类题目常见题型 的相关文章

随机推荐

  • 【LeetCode刷题日记】[641. 设计循环双端队列]

    LeetCode刷题日记 641 设计循环双端队列 题目描述 设计实现双端队列 你的实现需要支持以下操作 xff1a MyCircularDeque k xff1a 构造函数 双端队列的大小为k insertFront xff1a 将一个元

  • 【LeetCode刷题日记】[641. 设计循环双端队列]

    LeetCode刷题日记 641 设计循环双端队列 题目描述 设计实现双端队列 你的实现需要支持以下操作 xff1a MyCircularDeque k xff1a 构造函数 双端队列的大小为k insertFront xff1a 将一个元

  • 【LeetCode刷题日记】[313. 超级丑数]

    LeetCode刷题日记 313 超级丑数 题目描述 超级丑数 是一个正整数 xff0c 并满足其所有质因数都出现在质数数组 primes 中 给你一个整数 n 和一个整数数组 primes xff0c 返回第 n 个 超级丑数 题目数据保

  • 【LeetCode刷题日记】[413. 等差数列划分]

    LeetCode刷题日记 413 等差数列划分 题目描述 如果一个数列 至少有三个元素 xff0c 并且任意两个相邻元素之差相同 xff0c 则称该数列为等差数列 例如 xff0c 1 3 5 7 9 7 7 7 7 和 3 1 5 9 都

  • boost初探-日期与时间

    文章目录 一 前言二 boost基本概念三 日期与时间1 timer2 progress timer3 data time库3 1gregorian3 2date period 4 posix time 一 前言 之前写了两篇关于在linu

  • Runtime（运行时）是什么意思

    什么是 runtime 在计算机领域中 xff0c 经常会接触到 runtime 这个概念 xff0c 那么 runtime 究竟是什么东西 xff1f runtime 描述了程序运行时候执行的软件 指令 xff0c 在每种语言有着不同的实

  • 【C/C++开源库】C/C++矩阵运算开源库

    文章目录 一 C 43 43 矩阵运算库 eigen1 下载及安装1 1Linux安装及配置1 2Windows配置 2 测试使用2 1DevC 43 43 2 2Clion 3 深入学习 二 C 43 43 矩阵运算库 Armadillo

  • Cannot resolve plugin org.apache.maven.plugins:maven-resources-plugin:3.2.0

    一 概述 过了个周末回来更新代码之后 xff0c 重新built之后 xff0c 竟然built失败了 xff0c 提示信息为 xff1a Cannot resolve plugin org apache maven plugins mav

  • 并行计算之OpenMP入门简介

    转载于 xff1a https www cnblogs com kuliuheng p 4059133 html OpenMp提供了对于并行描述的高层抽象 xff0c 降低了并行编程的难度和复杂度 xff0c 这样程序员可以把更多的精力投入

  • PHP + Apache + Mysql集成环境部署及简要教程

    文章目录 PHP运行原理和机制PHP 的设计理念及特点PHP 的四层体系1 Zend 引擎 xff08 核心 xff09 2 Extensions xff08 扩展 xff09 3 SAPI xff08 服务器应用程序编程接口 xff09

  • 不同行业公司工资对比，计算机YYDS

    一 纳税标准 推荐一篇文章 xff1a 扣除社保 公积金年后 社保和公积金的扣除比例是22 左右 xff0c 工资在扣完社保和公积金的基础上再进行个税的扣除 税前19 2w xff0c 税前平均每月1 6w xff0c 扣除社保 公积金后年

  • 对实时操作系统多任务的一些理解

    一 什么是优先级反转 优先级反转 xff0c 是指在使用信号量时 xff0c 可能会出现的这样一种不合理的现象 xff0c 即 xff1a 优先级反转是指一个低优先级的任务持有一个被高优先级任务所需要的共享资源 高优先任务由于因资源缺乏而处

  • 【LeetCode刷题日记】数组和链表性质总结

    一 数据结构的存储方式 数据结构的存储方式只有两种 xff1a 数组 xff08 顺序存储 xff09 和链表 xff08 链式存储 xff09 这句话怎么理解 xff0c 不是还有散列表 栈 队列 堆 树 图等等各种数据结构吗 xff1f

  • C语言面向对象实现滑动均值滤波与平均值滤波

    文章目录 一 背景二 平均值滤波1 算法介绍2 代码实现3 实例 三 滑动均值滤波 xff08 Moving Average xff09 四 C语言面向面向对象实现滑动均值滤波 一 背景 在实际的数据采集中 xff0c 我们经常会取多次数据

  • 【LeetCode刷题日记】常用算法基础和理解及运用

    在我们LeetCode刷题过程中 xff0c 如果我们只是了解数据结构 xff08 数组 xff0c 链表 xff0c 数 xff09 的使用方法 xff0c 那我们在面对复杂的题目时 xff0c 是很难很好的解决问题的 xff0c 因此我

  • 【LeetCode刷题日记】数组类题目常见题型

    文章目录 303 区域和检索 数组不可变 https leetcode cn com problems range sum query immutable 304 二维区域和检索 矩阵不可变 https leetcode cn com pr

  • 【LeetCode刷题日记】队列类题目常见题型

    文章目录 225 用队列实现栈 https leetcode cn com problems implement stack using queues 剑指 Offer 09 用两个栈实现队列 https leetcode cn com p

  • 【LeetCode刷题日记】栈类题目常见题型

    文章目录 20 有效的括号 https leetcode cn com problems valid parentheses 225 用队列实现栈 https leetcode cn com problems implement stack

  • 回顾 nexus maven-snapshots 401 Unauthorized

    1 修改maven settings 文件 私库的用户名和密码 lt server gt lt id gt maven releases lt id gt lt username gt admin lt username gt lt pas

  • 【LeetCode刷题日记】树类题目常见题型

    文章目录 树基础知识 104 二叉树的最大深度 https leetcode cn com problems maximum depth of binary tree 102 二叉树的层序遍历 https leetcode cn com p

热门标签