遞歸的魅力（樹篇）

通過樹來了解遞歸

• • 翻轉二叉樹 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;
    }