递归：当前子节点执行完毕后，返回到父节点执行其他子节点

说明

力扣有详细的题解，我就不多说了，但给主要的代码加上了注释
力扣116题 ， 力扣117题 ，力扣236题

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

//这题用队列做做合适，横着一队一队的，就像队列一样，递归需要有自相似性
class Solution {
public:
    Node* connect(Node* root) {
        if (root == NULL) return root;
        // 初始化队列同时将第一层节点加入队列中，即根节点
        queue<Node*> q;
        q.push(root);
        // 外层的 while 循环迭代的是层数
        while (!q.empty()) {
            // 记录当前队列大小
            int sz = q.size();
            // 遍历这一层的所有节点
            for(int i = 0; i < sz; i++) {
                // 从队首取出元素
                Node* node = q.front();
                q.pop();
                // 这时node是q.front()的前一个节点
                if (i < sz - 1) node->next = q.front();
                // 拓展下一层节点
                if (node->left != NULL) q.push(node->left);
                if (node->right != NULL) q.push(node->right);
            }
        }
        // 返回根节点
        return root;
    }
};

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

class Solution {
public:
    Node* connect(Node* root) {
        if (root == NULL) return root;
        // 初始化队列同时将第一层节点加入队列中，即根节点
        queue<Node*> q;
        q.push(root);
        // 外层的 while 循环迭代的是层数
        while (!q.empty()) {
            // 记录当前队列大小
            int sz = q.size();
            // 遍历这一层的所有节点
            for(int i = 0; i < sz; i++) {
                // 从队首取出元素
                Node* node = q.front();
                q.pop();
                // 这时node是q.front()的前一个节点
                if (i < sz - 1) node->next = q.front();
                // 拓展下一层节点
                if (node->left != NULL) q.push(node->left);
                if (node->right != NULL) q.push(node->right);
            }
        }
        // 返回根节点
        return root;
    }
};

没看错，代码一样。

二叉树的最近公共祖先

问：为什么确定找到的就是答案？找到以后还有符合条件的节点吗？

答：因为在递归代码之后，属于递归树的从叶子到根的上升阶段。所以找到的第一个满足条件的一定是最深的。在满足条件的节点再往上走，即它的父节点肯定是一个子树满足（就是答案），一个子树不满足（因为答案唯一）。故找到的第一个也是最后一个满足条件的节点。

到底后，按着左右根的顺序，其实是后序遍历中完成最近公共祖先的查找

递归：当前子节点执行完毕后，返回到父节点执行其他子节点

class Solution {
public:
    TreeNode* ans;
    //在先序遍历中完成最近公共祖先的查找
    bool dfs(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL) return false;//如果root空则返回假
        bool lson = dfs(root->left, p, q);//递归左子树
        bool rson = dfs(root->right, p, q);//递归右子树
//如果左右子树不空 或者 当前点等于p或q且左右子树不空，则当前点就是答案
        if ((lson==true && rson==true) || ((root->val == p->val || root->val == q->val) && (lson==true || rson==true))) {
            ans = root;
        } 
        //向下深度查找左右子树是否含有p或q，并向上返回查找值。
        return lson==true || rson==true || root->val==p->val || root->val==q->val;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root, p, q);
        return ans;
    }
};