递归的魅力（树篇）

通过树来了解递归

• • 翻转二叉树 Easy
  • 填充二叉树节点的右侧指针 Midium
  • 二叉树展开为链表 Midium

要说的是，关于递归，要去相信递归函数的作用，不要跳入递归，下面来感受下递归的魅力

翻转二叉树 Easy

226. 翻转二叉树 - 力扣（LeetCode） (leetcode-cn.com) Easy

TreeNode* invertTree(TreeNode* root) { 
    //这个函数的作用就是翻转以root为结点的左右子树，并返回根结点
        if(root==nullptr){
            return root;
        }
        TreeNode *temp=root->left;
        root->left=root->right;
        root->right=temp;

        invertTree(root->left); //翻转以root左子树根为结点的左右子树
        invertTree(root->right);//翻转以root右子树根为结点的左右子树
        
        return root;
    }
           

填充二叉树节点的右侧指针 Midium

116. 填充每个节点的下一个右侧节点指针 - 力扣（LeetCode） (leetcode-cn.com) Midium

Node* connect(Node* root) {
        if(root==nullptr){
            return root;
        }
        connectTowNode(root->left,root->right);
        return root;
    }

    void connectTowNode(Node* node1,Node* node2){
        //这个函数的作用就是连接node1->node2
        if(node1==nullptr||node2==nullptr){
            return ;
        }

        node1->next=node2;  //首先是根结点连接

        //递归连接
        connectTowNode(node1->left,node1->right);
        connectTowNode(node2->left,node2->right);
        connectTowNode(node1->right,node2->left);
    }
           

二叉树展开为链表 Midium

114. 二叉树展开为链表 - 力扣（LeetCode） (leetcode-cn.com) Midium

void flatten(TreeNode* root) {//作用就是将以root为根节点的子树拉平为链表
        if(root==nullptr){
            return;
        }
        flatten(root->left);
        flatten(root->right);

    //拉平的过程，是把左子树放到右子树，然后原来的右子树再拼到当前右子树（原左子树）的右子树位置
        TreeNode *left=root->left;
        TreeNode *right=root->right;

        root->left=nullptr;
        root->right=left;

        TreeNode *p=root;
        while(p->right!=nullptr){
            p=p->right;
        }
        p->right=right;
    }