2022/11/12 题目练习

114. 二叉树展开为链表

题解:

1. 通过函数定义解决
2. 先把当前节点的左子树拉开
3. 再把当前节点的右子树拉开
4. 当前节点的左子树指向null
5. 当前节点的右子树指向拉开后的左子树
6. 用p指针遍历到右子树末端
7. 把拉开后的右子树拼接到上一步右子树末端

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function(root) {
    if(!root) {
        return;
    }
    flatten(root.left);
    flatten(root.right);
    let left = root.left;
    let right = root.right;
    root.left = null;
    root.right = left;
    let p = root;
    while(p.right) {
        p = p.right;
    }
    p.right = right;
};
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

654. 最大二叉树

题解:

1. 找到数组中最大的元素, 并记录其值和下标
2. 以最大元素创建二叉树
3. 二叉树的左子树由最大元素左边的元素构成
4. 二叉树的右子树由最大元素右边元素构成
5. 左右子树都满足递归定义

/**
 * 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* constructMaximumBinaryTree(vector<int>& nums) {
        return build(nums, 0, nums.size() - 1);
    }
    TreeNode* build(const vector<int>& nums, int low, int high) {
        if(low > high) {
            return nullptr;
        }
        int index = low;
        for(int i = low + 1; i <= high; i++) {
            if(nums[i] > nums[index]) {
                index = i;
            }
        }
        TreeNode* root = new TreeNode(nums[index]);
        root->left = build(nums, low, index - 1);
        root->right = build(nums, index + 1, high);
        return 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

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

题解

1. 先确定根元素
2. 通过前序和中序遍历得出左子树和右子树
   

/**
 * 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> hash;
    TreeNode* build(vector<int>& pre, int pleft, int pright,
                    vector<int>& ino, int ileft, int iright) {
                        if(pleft > pright) {
                            return nullptr;
                        }
                        TreeNode* root = new TreeNode(pre[pleft]);
                        int index;
                        for(int i = ileft; i <= iright; i++) {
                            if(ino[i] == pre[pleft]) {
                                index = i;
                            }
                        }
                        root->left = build(pre, pleft + 1, pleft + index - ileft,
                                            ino, ileft, index - 1);
                        root->right = build(pre, pleft + index - ileft + 1, pright, 
                                            ino, index + 1, iright);
                        return root;
                    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return build(preorder, 0, preorder.size() - 1,
                    inorder, 0, inorder.size() - 1);
    }
};
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

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