Leetcode 3.15

二叉树

1.二叉搜索树中第K小的元素

二叉搜索树中第K小的元素

最重要的知识点：二叉树搜索树的中序遍历是升序的。
方法一：我们只需存储升序遍历，返回升序遍历的结果即可。

/**
 * 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> ans;
    int kthSmallest(TreeNode* root, int k) {
        dfs(root);
        return ans[k - 1];
    }
    void dfs(TreeNode* root) {
        if (root == nullptr) return;
        dfs(root->left);
        ans.push_back(root->val);
        dfs(root->right);    
    }
};

改进：我们还可以在找到答案后停止，不需要遍历整棵树。

/**
 * 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 kthSmallest(TreeNode* root, int k) {
        dfs(root, k);
        return ans;
    }
    void dfs(TreeNode* root, int &k) {
        if (root == nullptr) return;
        dfs(root->left, k);
        if (--k == 0) {
            ans = root->val;
            return;
        }
        dfs(root->right, k);    
    }
};

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:
    void flatten(TreeNode* root) {
        vector<TreeNode*> ans;
        dfs(root, ans);
        for (int i = 1; i < ans.size(); i++) {
            //前一个节点
            auto *pre = ans.at(i - 1);
            //当前节点
            auto *cur = ans.at(i);
            pre->left = nullptr;
            pre->right = cur; 
        }
    }
    void dfs(TreeNode* root, vector<TreeNode*> &ans) {
        if (root == nullptr) return;
        ans.push_back(root);
        dfs(root->left, ans);
        dfs(root->right, ans);      
    }
};

思路二：更便捷的递归
参考
这个问题其实是分为三步：

• 首先将根节点的左子树变成链表
• 其次将根节点的右子树变成链表
• 最后将变成链表的右子树放在变成链表的左子树的最右边

这就是一个递归的过程，递归的一个非常重要的点就是：不去管函数的内部细节是如何处理的，我们只看其函数作用以及输入与输出。对于函数flatten来说：

函数作用：将一个二叉树，原地将它展开为链表
输入：树的根节点
输出：无

/**
 * 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 flatten(TreeNode* root) {
        if (root == nullptr) return;
        //展开左子树为链表
        flatten(root->left);
        //展开子树为链表
        flatten(root->right);
        auto l = root->left;
        auto r = root->right;
        //左子树置空
        root->left = nullptr;
        //左子树移动到右子树
        root->right = l;
        //指针指向右子树最后一个节点
        while (root->right != nullptr) root = root->right;
        //指向右子树
        root->right = r;
    }
};

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

从前序与中序遍历序列构造二叉树
根据前序和中序遍历我们可以确定二叉树的根节点，左子树和右子树，不断递归得到结果。比较复杂的是确定左右子树的边界。借助map来快速确定元素在inorder中的位置，这副图中的边界位置建议仔细推导。
需要注意的点：前序遍历中，左子树的右边界 需要借助 中序遍历中 左子树的个数 来辅助确定。

/**
 * 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* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        if (!n) return nullptr;
        unordered_map<int, int> mp;
        for (int i = 0; i < n; i++) {
            mp[inorder[i]] = i;
        }
        return dfs(preorder, 0, n - 1, mp, 0, n - 1);
    }
    TreeNode* dfs(vector<int>& preorder, int preleft, int preright,
                unordered_map<int, int>& mp, int inleft, int intright) {
        if (preright < preleft || inleft > intright) return nullptr;
        TreeNode* ans = new TreeNode(preorder[preleft]);
        ans->left = dfs(preorder, preleft + 1, mp[preorder[preleft]] + preleft - inleft, 
                    mp, inleft, mp[preorder[preleft]] - 1);
        ans->right = dfs(preorder, mp[preorder[preleft]] + preleft - inleft + 1, preright, 
                    mp, mp[preorder[preleft]] + 1, intright);
        return ans;
    }

};