LeetCode基础_树

[116] 填充每个节点的下一个右侧节点指针

class Solution {
public:
    Node *connect(Node *root) {   //每次的目的都是连接下一层的节点：left连接right，right连接root->next的left
        if (!root || !root->left) //当前为null或没有孩子节点(完美二叉树，孩子有则必有俩)，则没有必要连接，直接退出
            return root;
        root->left->next = root->right;
        if (root->next && root->next->left) //完美二叉树，(当前节点有孩子，则next也一定有)，为保证可读性没有舍去
            root->right->next = root->next->left;

        //本root的left和right连接完了 递归连接孩子层的
        connect(root->left);
        connect(root->right);
        return root;
    }
};

[117] 填充每个节点的下一个右侧节点指针 II

class Solution {
public:
    Node *connect(Node *root) {
        if (!root)
            return root;

        Node *next_node = nextNode(root->next); //只用来找右孩子该连的next(假设有右孩子)
        if (root->left)
            root->left->next = root->right ? root->right : next_node;
        if (root->right)
            root->right->next = next_node;

        connect(root->right); //!!注意1，这里是dfs，一定要连接好先右侧再连接左侧，否则左侧会找不到next
        connect(root->left);
        return root;
    }
    //注意2，一定要有nextNode函数，负责找child应该连接的next节点
    Node *nextNode(Node *root_next) {
        while (root_next != nullptr) {
            if (root_next->left || root_next->right)
                return root_next->left ? root_next->left : root_next->right;
            else
                root_next = root_next->next;
        }
        return nullptr; //已知找到root没有next
    }
};

注意踩坑：
case1:
case2:

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

class Solution {
public:
    //优化思路:遍历一遍树，记录每个节点的左右孩子，左孩子比root小 右节点反之
    //若删除一个点如6，则从跟节点出发一直走到6的点都要更新下列map，路程中的所有点若比6大 left_child减1，反之right_child减1
    // map<TreeNode *, int> nb_left_childs_;
    // map<TreeNode *, int> nb_right_childs_;

    //此题二叉搜索树第k小，则转换思路，中序遍历第k个节点即可。
    //思路:每遍历一个点now+1,当now==k时，find为true及时返回
    void recurse(TreeNode *root, bool &find, int &now, int &ret, int &k) {
        if (find || !root)
            return;
        recurse(root->left, find, now, ret, k);
        ++now; //第now小的点，每新遍历一个点，都要++
        if (now == k) {
            find = true;
            ret = root->val;
        }
        recurse(root->right, find, now, ret, k);
    }
    int kthSmallest(TreeNode *root, int k) {
        bool find = false;
        int ret = 0, now = 0;
        recurse(root, find, now, ret, k);
        return ret;
    }
};

LeetCode基础_树

原文：https://www.cnblogs.com/Shaw99/p/13335548.html