LeetCode Hot100 Tree

Posted on Edited on

二叉树的中序遍历

Problem

https://leetcode.cn/problems/binary-tree-inorder-traversal/description/?envType=study-plan-v2&envId=top-100-liked

Solution

递归版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 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:

    void inorder(TreeNode *root, vector<int> &ans)
    {
        if (root == nullptr) return;

        inorder(root->left, ans);
        ans.push_back(root->val);
        inorder(root->right, ans);
    }

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        inorder(root, ans);
        return ans;
    }
};

迭代版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 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<int> inorderTraversal(TreeNode* root) {

        vector<int> ans;
        stack<TreeNode *> stk;
        TreeNode *cur = root;

        while (cur || !stk.empty())
        {
            while (cur)
            {
                stk.push(cur);
                cur = cur->left;
            }

            TreeNode *v = stk.top();
            stk.pop();
            ans.push_back(v->val);
            cur = v->right;
        }

        return ans;
    }
};

二叉树的前序遍历

Problem

https://leetcode.cn/problems/binary-tree-preorder-traversal/description/

Solution

递归版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 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:

    void preorder(TreeNode *root, vector<int> &ans)
    {
        if (root == nullptr) return;

        ans.push_back(root->val);
        preorder(root->left, ans);
        preorder(root->right, ans);
    }

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

迭代版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * 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:

    void preorder(TreeNode *root, vector<int> &ans)
    {
        if (root == nullptr) return;

        ans.push_back(root->val);
        preorder(root->left, ans);
        preorder(root->right, ans);
    }

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;

        TreeNode *cur = root;

        stack<TreeNode *> stk;

        while (cur || !stk.empty())
        {
            while (cur)
            {
                ans.push_back(cur->val);
                stk.push(cur);
                cur = cur->left;
            }

            TreeNode *top = stk.top();
            stk.pop();
            cur = top->right;
        }

        return ans;
    }
};

N叉树的前序遍历

Problem

https://leetcode.cn/problems/n-ary-tree-preorder-traversal/description/

Solution

递归版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:

    void preorder(Node *root, vector<int> &ans)
    {
        if (root == nullptr) return;

        ans.push_back(root->val);

        for (Node *child : root->children)
        {
            preorder(child, ans);
        }
    }

    vector<int> preorder(Node* root) {
        vector<int> ans;
        preorder(root, ans);
        return ans;
    }
};

迭代版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<int> preorder(Node* root) {

        if (root == nullptr) return {};

        stack<Node *> stk;
        stk.push(root);
        vector<int> ans;

        while (!stk.empty())
        {
            Node *top = stk.top();
            stk.pop();
            if (top)
            {
                for (int i = top->children.size()-1; i >= 0; i --)
                {
                    if (top->children[i])
                    {
                        stk.push(top->children[i]);
                    }
                }

                stk.push(top);
                stk.push(nullptr);
            }
            else
            {
                Node *cur = stk.top();
                stk.pop();
                if (cur)
                    ans.push_back(cur->val);

            }
        }
        return ans;
    }
};

二叉树的后序遍历

Probelm

https://leetcode.cn/problems/binary-tree-postorder-traversal/description/

Solution

递归版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 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:

    void postorder(TreeNode *root, vector<int> &ans)
    {
        if (root == nullptr) return;

        postorder(root->left, ans);
        postorder(root->right, ans);
        ans.push_back(root->val);
    }

    vector<int> postorderTraversal(TreeNode* root) {

        vector<int> ans;
        postorder(root, ans);
        return ans;
    }
};

迭代版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * 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<int> postorderTraversal(TreeNode* root) {

        if (root == nullptr) return {};
        stack<TreeNode *> stk;
        stk.push(root);

        vector<int> ans;

        while (!stk.empty())
        {
            TreeNode *top = stk.top();
            stk.pop();
            if (top)
            {
                stk.push(top);
                stk.push(nullptr);

                if (top->right)
                    stk.push(top->right);
                if (top->left)
                    stk.push(top->left);
            }
            else
            {
                TreeNode *cur = stk.top();
                stk.pop();
                if (cur)
                    ans.push_back(cur->val);
            }
        }

        return ans;
    }
};

二叉树的最大深度

Probelm

https://leetcode.cn/problems/maximum-depth-of-binary-tree/?envType=study-plan-v2&envId=top-100-liked

Solution

一个二叉树的最大深度为其左子树最大深度和右子树最大深度中的最大值+1，空节点深度为0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * 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) {
        return root ? max(maxDepth(root->left), maxDepth(root->right)) + 1 : 0;
    }
};

反转二叉树

Problem

https://leetcode.cn/problems/invert-binary-tree/?envType=study-plan-v2&envId=top-100-liked

Solution

反转二叉树等于反转根节点左子树和右子树后，交换左右子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 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:
    TreeNode* invertTree(TreeNode* root) {

        if (root == nullptr) return nullptr;

        TreeNode *l = root->left;
        root->left = invertTree(root->right);
        root->right = invertTree(l);

        return root;
    }
};

对称二叉树

Problem

https://leetcode.cn/problems/symmetric-tree/description/?envType=study-plan-v2&envId=top-100-liked

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 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:

    bool check(TreeNode *root_left, TreeNode *root_right)
    {
        if (!root_left && !root_right) return true;

        if (root_left && root_right && root_left->val == root_right->val)
        {
            return check(root_left->left, root_right->right) && check(root_left->right, root_right->left);
        }

        return false;
    }

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

二叉树的直径

Problem

https://leetcode.cn/problems/diameter-of-binary-tree/?envType=study-plan-v2&envId=top-100-liked

Solution

深度优先搜索遍历二叉树求二叉树中每棵子树的深度，左子树的最大深度+右子树的最大深度即为二叉树的直径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 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 ans;

    int dfs(TreeNode *root)
    {
        if (root == nullptr) return 0;

        int left_depth = dfs(root->left);
        int right_depth = dfs(root->right);

        ans = max(ans, left_depth + right_depth);

        return max(left_depth, right_depth) + 1;
    }

    int diameterOfBinaryTree(TreeNode* root) {
        ans = 0;
        dfs(root);
        return ans;
    }
};

二叉树的层序遍历

Problem

https://leetcode.cn/problems/binary-tree-level-order-traversal/?envType=study-plan-v2&envId=top-100-liked

Solution

root为空直接返回；记录当前队列size，这个size就是一层节点的数量，依次将这层节点出队，val放入ans，并将其非空子节点入队，直到队列为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * 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>> ans;
        if (root == nullptr) return ans;

        queue<TreeNode *> q;

        q.push(root);

        while (!q.empty())
        {
            int size = q.size();
            vector<int> level_ans;
            for (int i = 0; i < size; i ++)
            {
                TreeNode *front = q.front();
                q.pop();
                level_ans.push_back(front->val);

                if (front->left)
                    q.push(front->left);

                if (front->right)
                    q.push(front->right);
            }

            ans.push_back(level_ans);
        }
        return ans;
    }
};

将有序数组转换为二叉搜索树

Problem

https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/?envType=study-plan-v2&envId=top-100-liked

Solution

二叉搜索树左子树的节点小于等于根节点的值，右子树的节点大于等于根节点的值，升序数组，将中间的值当成根节点，左边一半左子树，右边一半右子树，递归的构造。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * 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:

    TreeNode *sortArrayToBST(vector<int> &nums, int left, int right)
    {
        if (left >= right) return nullptr;
        int mid = (left + right) / 2;

        TreeNode *left_node = sortArrayToBST(nums, left, mid);
        TreeNode *right_node = sortArrayToBST(nums, mid + 1, right);
        TreeNode *root = new TreeNode(nums[mid], left_node, right_node);

        return root;
    }

    TreeNode* sortedArrayToBST(vector<int>& nums) {

        int size = nums.size();

        return sortArrayToBST(nums, 0, size);
    }
};

验证搜索二叉树

Problem

https://leetcode.cn/problems/validate-binary-search-tree/?envType=study-plan-v2&envId=top-100-liked

Solution

深度优先搜索遍历二叉树，顺便求每个树的最大值和最小值，用这个值和根节点的值最比较判断是否符合二叉搜索树的特点。由于测试数据有INT_MAX所以要开long long

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * 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:

    bool getMaxAndMin(TreeNode *root, long long &max_val, long long &min_val)
    {
        if (root == nullptr)
        {
            max_val = LONG_MIN;
            min_val = LONG_MAX;
            return true;
        }

        long long max_left_val = 0;
        long long min_left_val = 0;
        bool left_flag = getMaxAndMin(root->left, max_left_val, min_left_val);

        long long max_right_val = 0;
        long long min_right_val = 0;
        bool right_flag = getMaxAndMin(root->right, max_right_val, min_right_val);

        max_val = max(max(max_left_val, max_right_val), (long long)root->val);
        min_val = min(min(min_left_val, min_right_val), (long long)root->val);

        return root->val > max_left_val && root->val < min_right_val && left_flag && right_flag;
    }

    bool isValidBST(TreeNode* root) {
        if (root == nullptr) return true;

        long long max_val = 0, min_val = 0;
        return getMaxAndMin(root, max_val, min_val);
    }
};

二叉树中第K小的元素

Problem

https://leetcode.cn/problems/kth-smallest-element-in-a-bst/description/?envType=study-plan-v2&envId=top-100-liked

Solution

二叉搜索树的中序遍历是升序的，按照中序遍历二叉搜索树，第k个遍历到的即为k小的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * 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 kthSmallest(TreeNode* root, int k) {

        stack<TreeNode *> stk;

        TreeNode *cur = root;

        int count = 0;

        while (cur || !stk.empty())
        {
            while (cur)
            {
                stk.push(cur);
                cur = cur->left;
            }

            TreeNode *top = stk.top();
            stk.pop();

            count ++;

            if (count == k) return top->val;

            cur = top->right;
        }

        return -1;
    }
};

二叉树的右视图

Problem

https://leetcode.cn/problems/binary-tree-right-side-view/?envType=study-plan-v2&envId=top-100-liked

Solution

右视图包含每层的最后一个元素，层序遍历二叉树，取每层的最后一个元素即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * 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<int> rightSideView(TreeNode* root) {

        if (root == nullptr) return {};

        queue<TreeNode *> q;
        vector<int> ans;
        q.push(root);

        while (!q.empty())
        {
            int size = q.size();

            for (int i = 0; i < size; i ++)
            {
                TreeNode *front = q.front();
                q.pop();
                if (i == size - 1)
                {
                    ans.push_back(front->val);
                }

                if (front->left)
                    q.push(front->left);
                if (front->right)
                    q.push(front->right);
            }
        }

        return ans;
    }
};

二叉树展开为链表

Problem

https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/description/?envType=study-plan-v2&envId=top-100-liked

Solution

若有左子树，先flatten左子树并记录左子树里最后访问的节点（对于先序遍历来说最后访问的节点就是从根节点开始一直向右走的节点，所以递归有点多余），将flatten后的左子树接入root和右子树之间，若左子树为空直接处理右子树，递归的处理即可，要记得将左子树置空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * 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:

    TreeNode *flattenRetLast(TreeNode *root)
    {
        if (root == nullptr) return nullptr;

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

        TreeNode *ret = root;
        TreeNode *root_right = root->right;
        if (root->left != nullptr)
        {
            ret = flattenRetLast(root->left);
            ret->left = nullptr;
            ret->right = root->right;
            root->right = root->left;
            root->left = nullptr;
        }

        if (root_right != nullptr)
        {
            ret = flattenRetLast(root_right);
        }

        return ret;
    }

    void flatten(TreeNode* root) {

        flattenRetLast(root);
    }
};

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

Problem

https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/?envType=study-plan-v2&envId=top-100-liked

Solution

首先构造节点值到中序遍历idx的map，保证从preorder拿到值得时候可以O(1)的找到在inorder中的位置，先序遍历的第一个元素即为根节点，找到这个节点在中序遍历中的位置，左边是左子树，右边是右子树，算出左子树的节点数目，这样就可以在先序遍历中找到左子树的范围和右子树的范围，递归的处理即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * 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:

    unordered_map<int, int> node2inidx;

    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder, int pre_l, int pre_r, int in_l, int in_r)
    {
        if (pre_l > pre_r || in_l > in_r) return nullptr;

        if (pre_l == pre_r && in_l == in_r) return new TreeNode(preorder[pre_l]);

        int root_val = preorder[pre_l];
        int root_inidx = node2inidx[root_val];

        int left_len = root_inidx -  in_l;

        return new TreeNode(root_val,
                            buildTree(preorder, inorder, pre_l+1, pre_l + left_len, in_l, root_inidx-1),
                            buildTree(preorder, inorder, pre_l + left_len + 1, pre_r, root_inidx+1, in_r));
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {

        int n = inorder.size();
        for (int i = 0; i < n; i ++)
        {
            node2inidx[inorder[i]] = i;
        }

        return buildTree(preorder, inorder, 0, n-1, 0, n-1);
    }
};

路经总和III

Problem

https://leetcode.cn/problems/path-sum-iii/description/?envType=study-plan-v2&envId=top-100-liked

Solution

深度优先搜索遍历二叉树，记录自上至下的前缀和及其个数，当前前缀和-目标值如果是某个节点的前缀和，说明某个节点到当前节点的路径和为目标值。以当前节点为根节点的子树符合要求路径条数等于以左子树为根节点的路径条数加右子树为根节点的路径条数加以当前节点为最终节点的路径条数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * 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:

    unordered_map<long long, int> prefix_sum_count;
    int target_sum;

    int dfs(TreeNode *root, long long sum)
    {
        if (root == nullptr)
        {
            return 0;
        }

        long long cur_sum = sum + root->val;

        int ret = 0;
        if (prefix_sum_count.count(cur_sum - target_sum))
        {
            ret += prefix_sum_count[cur_sum - target_sum];
        }

        prefix_sum_count[cur_sum] ++;
        ret += dfs(root->left, cur_sum);
        ret += dfs(root->right, cur_sum);
        prefix_sum_count[cur_sum] --;

        return ret;
    }

    int pathSum(TreeNode* root, int targetSum) {

        target_sum = targetSum;
        prefix_sum_count[0] = 1;

        return dfs(root, 0);
    }
};

二叉树的最近公共祖先

Problem

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/?envType=study-plan-v2&envId=top-100-liked

Solution

深度优先搜索遍历二叉树，记录根节点左子树右子树中是否有p或q，满足left_flag && right_flag || root_flag && left_flag || root_flag && right_flag即为所求节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *ans;
    bool dfs(TreeNode *root, TreeNode *p, TreeNode *q)
    {
        if (root == nullptr) return false;

        bool root_flag = (root == p || root == q);
        bool left_flag = dfs(root->left, p, q);
        bool right_flag = dfs(root->right, p, q);

        if (left_flag && right_flag || root_flag && left_flag || root_flag && right_flag)
        {
            ans = root;
        }

        return root_flag || left_flag || right_flag;
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

        ans == nullptr;

        dfs(root, p, q);

        return ans;
    }
};

二叉树中的最大路径和

Problem

https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/?envType=study-plan-v2&envId=top-100-liked

Solution

深度优先搜索遍历二叉树，求出每棵子树从根节点开始可向上提供的最大和，节点间的路径和可以看成是根节点值+左子树可提供的最大和+右子树的可提供的最大和，在子树所提供最大和小于0时需要忽略这棵子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 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 ans;

    int dfs(TreeNode *root)
    {
        if (root == nullptr) return 0;

        int left = max(0, dfs(root->left));
        int right = max(0, dfs(root->right));

        ans = max(root->val + left + right, ans);

        return root->val + max(left, right);
    }

    int maxPathSum(TreeNode* root) {

        ans = INT_MIN;
        dfs(root);

        return ans;
    }
};