LeetCode算法練習(xí)——深度優(yōu)先搜索 DFS

更多干貨就在我的個(gè)人博客 BlackBlog.tech 歡迎關(guān)注！
也可以關(guān)注我的csdn博客：黑哥的博客
謝謝大家！

網(wǎng)上大部分LeetCode的代碼都沒有給出注釋和解釋，對(duì)于新手學(xué)習(xí)很不方便。筆者在這里盡力給每一句代碼都寫上注釋，每一道題最后都有解釋。

很久都沒有刷LeetCode了，上次LeetCode已經(jīng)快是兩個(gè)月之前的事情了?，F(xiàn)在繼續(xù)。之前中級(jí)算法差不多刷完了，這次專練數(shù)據(jù)結(jié)構(gòu)。這一篇主要是dfs題目，標(biāo)識(shí)為簡(jiǎn)單的題目一般就跳過了，主要刷中等與困難題。
LeetCode上分類為dfs的題目大多數(shù)與樹相關(guān)。
給個(gè)目錄：
LeetCode98 驗(yàn)證二叉搜索樹
LeetCode113 路徑總和 II
LeetCode105 從前序與中序遍歷序列構(gòu)造二叉樹
LeetCode106 從中序與后序遍歷序列構(gòu)造二叉樹
LeetCode129 求根到葉子節(jié)點(diǎn)數(shù)字之和
LeetCode124 二叉樹中的最大路徑和
LeetCode130 被圍繞的區(qū)域
LeetCode114 二叉樹展開為鏈表
LeetCode116 填充同一層的兄弟節(jié)點(diǎn)
LeetCode117 填充同一層的兄弟節(jié)點(diǎn) II

最后還有一波福利，一個(gè)TreeLinkNode的建樹調(diào)試代碼，官方?jīng)]有給出，自己搞了一份方便大家調(diào)試。

LeetCode98 驗(yàn)證二叉搜索樹

題目

給定一個(gè)二叉樹，判斷其是否是一個(gè)有效的二叉搜索樹。

一個(gè)二叉搜索樹具有如下特征：

節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。
節(jié)點(diǎn)的右子樹只包含大于當(dāng)前節(jié)點(diǎn)的數(shù)。
所有左子樹和右子樹自身必須也是二叉搜索樹。

示例1:

輸入:
    2
   / \
  1   3
輸出: true

示例2:

輸入:
    5
   / \
  1   4
     / \
    3   6
輸出: false
解釋: 輸入為: [5,1,4,null,null,3,6]。
     根節(jié)點(diǎn)的值為 5 ，但是其右子節(jié)點(diǎn)值為 4 。

C++代碼

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return dfs(root,LONG_MAX,LONG_MIN);
    }

    bool dfs(TreeNode* root, long max,long min){
        if(!root) return true;
        if(root->val<=min || root->val>=max) return false;
        else return (dfs(root->left,root->val,min) && dfs(root->right,max,root->val));
    }
};

體會(huì)

這個(gè)題利用了二叉檢索樹自身的性質(zhì)，左邊節(jié)點(diǎn)小于根節(jié)點(diǎn)，右邊節(jié)點(diǎn)大于根節(jié)點(diǎn)。初始化時(shí)帶入系統(tǒng)最大值和最小值，在遞歸過程中換成它們自己的節(jié)點(diǎn)值，用long代替int就是為了包括int的邊界條件。
如果這棵樹遍歷到了葉節(jié)點(diǎn)，則返回true。如果在遍歷的過程中出現(xiàn)了當(dāng)前節(jié)點(diǎn)大于等于父節(jié)點(diǎn)（左子樹）或小于等于父節(jié)點(diǎn)（右子樹）則返回false。對(duì)結(jié)果做&&運(yùn)算。返回最終的結(jié)果。

LeetCode113 路徑總和 II

題目

給定一個(gè)二叉樹和一個(gè)目標(biāo)和，找到所有從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)路徑總和等于給定目標(biāo)和的路徑。

說明: 葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。

示例:
給定如下二叉樹，以及目標(biāo)和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
返回:
[
   [5,4,11,2],
   [5,8,4,5]
]

C++代碼

class Solution {
public:
    vector<vector<int>> res; //最終結(jié)果
    vector<int> mark; //每一個(gè)小的路徑和
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        dfs(root,sum,0);
        return res;
    }

    void dfs(TreeNode* root,int sum,int now){
        if(!root) return;//葉節(jié)點(diǎn)直接返回
        if(sum == now+root->val && root->left == NULL && root->right == NULL){ //路經(jīng)總和滿足要求 且該節(jié)點(diǎn)是葉節(jié)點(diǎn)
            mark.push_back(root->val); //首先將當(dāng)前節(jié)點(diǎn)添加進(jìn) mark
            res.push_back(mark); //將mark添加到res中
            mark.pop_back(); //將當(dāng)前值從mark中彈出，因?yàn)楣?jié)點(diǎn)結(jié)束
            return; //返回
        }
        else{
            int tmp = now + root->val; //如果路徑還不滿足 繼續(xù)遍歷 先左后右
            mark.push_back(root->val); //把當(dāng)前節(jié)點(diǎn)的值放入mark
            dfs(root->left,sum,tmp);//遍歷左節(jié)點(diǎn)
            dfs(root->right,sum,tmp);//遍歷右節(jié)點(diǎn)
            mark.pop_back();//彈出當(dāng)前節(jié)點(diǎn)
            return;
        }
    }

};

體會(huì)

思路比較清晰，用dfs遍歷整個(gè)樹，一旦遇到葉節(jié)點(diǎn)且數(shù)據(jù)總和滿足sum，則將這個(gè)路徑保存到最終結(jié)果。中間使用mark記錄路徑，res保存最終符合條件的路徑。注意記錄路徑的過程中，mark中的數(shù)字要pop。

LeetCode105 從前序與中序遍歷序列構(gòu)造二叉樹

題目

根據(jù)一棵樹的前序遍歷與中序遍歷構(gòu)造二叉樹。

注意:
你可以假設(shè)樹中沒有重復(fù)的元素。

例如，給出

前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]

返回如下的二叉樹：

    3
   / \
  9  20
    /  \
   15   7

C++代碼

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size()==0 && inorder.size()==0) return NULL; //前序后序都為空，直接return NULL
        return myBuildTree(preorder,inorder,0,0,inorder.size()-1);
    }

    TreeNode* myBuildTree(vector<int>& preorder, vector<int>& inorder,int prestart,int instart,int inend){
        //prestart代表當(dāng)前子樹的根節(jié)點(diǎn)在preorder的位置，instart inend表示當(dāng)前子樹在inorder中的開頭和結(jié)尾 
        if ( prestart>preorder.size()-1 || inend < instart) return NULL; //如果inend<instart 或者 prestart超過了preorder的限制 表示葉節(jié)點(diǎn)，直接return NULL
        TreeNode *root = new TreeNode(preorder[prestart]); //新建一個(gè)節(jié)點(diǎn) root 當(dāng)前子樹的根節(jié)點(diǎn)
        int inindex = 0; //用于標(biāo)記根節(jié)點(diǎn)的值在前序中的位置
        //找inindex的位置
        for(int i=instart;i<=inend;i++){
            if(inorder[i] == preorder[prestart]){
                inindex = i;
                break;
            }
        }
        //左子樹,prestart后移動(dòng)一位，instart不變，inend為inindex-1
        root->left  = myBuildTree(preorder,inorder,prestart+1,instart,inindex-1);
        //右子樹，prestart變?yōu)閜restart+inindex-instart+1，也就是向后移動(dòng)其在中序遍歷中的位置離開頭的距離后+1，inend不變，instart變?yōu)閕nindex+1
        root->right = myBuildTree(preorder,inorder,prestart+inindex-instart+1,inindex+1,inend);
        //將子樹的根節(jié)點(diǎn)返回
        return root;
    }
};

體會(huì)

使用先序遍歷與中序遍歷重建二叉樹。通過先序遍歷，我們很好確定根節(jié)點(diǎn)。通過根節(jié)點(diǎn)在中序遍歷中的位置，我們可以確定一個(gè)樹的左子樹，與右子樹。對(duì)左子樹，右子樹做遞歸操作，每次都計(jì)算出根節(jié)點(diǎn)，將根節(jié)點(diǎn)與其父節(jié)點(diǎn)連接即可。
本題的解法利用元素下標(biāo)來確定子樹的先序和中序遍歷，也可以新建vector模擬這個(gè)過程，但是比較耗時(shí)。
唯一可能的難點(diǎn)就是右子樹建立時(shí)prestart的計(jì)算

LeetCode106 從中序與后序遍歷序列構(gòu)造二叉樹

題目

根據(jù)一棵樹的中序遍歷與后序遍歷構(gòu)造二叉樹。

注意:
你可以假設(shè)樹中沒有重復(fù)的元素。

例如，給出

中序遍歷 inorder = [9,3,15,20,7]
后序遍歷 postorder = [9,15,7,20,3]

返回如下的二叉樹：

    3
   / \
  9  20
    /  \
   15   7

C++代碼

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(inorder.size()==0 && postorder.size()==0) return NULL; //中序 后序都為空，則直接返回NULL
        return myBuildTree(inorder,postorder,postorder.size()-1,0,inorder.size()-1); //建樹
    }
    
    TreeNode* myBuildTree(vector<int>& inorder,vector<int>& postorder,int poststart,int instart,int inend){
        //poststart代表當(dāng)前子樹的根節(jié)點(diǎn)在postorder的位置，instart inend表示當(dāng)前子樹在inorder中的開頭和結(jié)尾 
        if(instart>inend || poststart<0) return NULL; //如果instart>inend 或者poststart<0 證明是葉節(jié)點(diǎn)，返回NULL
        TreeNode *root = new TreeNode(postorder[poststart]); //新建一個(gè)子樹的根節(jié)點(diǎn)
        int inindex=0;//表示根節(jié)點(diǎn)在inorder中的位置
        //尋找inindex的具體值
        for(int i=0;i<inorder.size();i++){
            if(inorder[i]==postorder[poststart]){
                inindex = i;
                break;
            }
        }
        //建立左子樹 poststart向前移動(dòng)inend-inindex位后再向前移動(dòng)一位，instart不變，inend變?yōu)閕nindex-1
        root->left = myBuildTree(inorder,postorder,poststart-1-(inend-inindex),instart,inindex-1);
        //建立右子樹 poststart向前移動(dòng)1位，instart變?yōu)閕nindex+1， inend保持不變
        root->right = myBuildTree(inorder,postorder,poststart-1,inindex+1,inend);
        //將子樹的根節(jié)點(diǎn)返回
        return root;
    }
};

體會(huì)

整體流程與上一題類似

使用中序遍歷與后序遍歷重建二叉樹。通過后序遍歷，我們很好確定根節(jié)點(diǎn)。通過根節(jié)點(diǎn)在中序遍歷中的位置，我們可以確定一個(gè)樹的左子樹，與右子樹。對(duì)左子樹，右子樹做遞歸操作，每次都計(jì)算出根節(jié)點(diǎn)，將根節(jié)點(diǎn)與其父節(jié)點(diǎn)連接即可。
唯一可能的難點(diǎn)就是左子樹建立時(shí)prestart的計(jì)算

LeetCode129 求根到葉子節(jié)點(diǎn)數(shù)字之和

題目

給定一個(gè)二叉樹，它的每個(gè)結(jié)點(diǎn)都存放一個(gè) 0-9 的數(shù)字，每條從根到葉子節(jié)點(diǎn)的路徑都代表一個(gè)數(shù)字。

例如，從根到葉子節(jié)點(diǎn)路徑 1->2->3 代表數(shù)字 123。

計(jì)算從根到葉子節(jié)點(diǎn)生成的所有數(shù)字之和。

說明: 葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。

示例 1:

輸入: [1,2,3]
    1
   / \
  2   3
輸出: 25
解釋:
從根到葉子節(jié)點(diǎn)路徑 1->2 代表數(shù)字 12.
從根到葉子節(jié)點(diǎn)路徑 1->3 代表數(shù)字 13.
因此，數(shù)字總和 = 12 + 13 = 25.

示例 2:

輸入: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
輸出: 1026
解釋:
從根到葉子節(jié)點(diǎn)路徑 4->9->5 代表數(shù)字 495.
從根到葉子節(jié)點(diǎn)路徑 4->9->1 代表數(shù)字 491.
從根到葉子節(jié)點(diǎn)路徑 4->0 代表數(shù)字 40.
因此，數(shù)字總和 = 495 + 491 + 40 = 1026.

C++代碼

class Solution {
public:
    vector<int> path; //記錄每次的路徑
    int sum_all = 0; //數(shù)字總和
    int sumNumbers(TreeNode* root) {
        dfs(root); //dfs開始
        return sum_all; //直接返回路徑和
    }
    
    void dfs(TreeNode* root){
        if(!root) return; //如果是空節(jié)點(diǎn)直接返回
        if(root->left==NULL && root->right ==NULL){ //如果是葉節(jié)點(diǎn)
            path.push_back(root->val); //現(xiàn)將val存入path
            sum_all += count(path); //計(jì)算這一個(gè)path的數(shù)字和
            path.pop_back(); //彈出value
        }
        else{ //如果不是葉節(jié)點(diǎn)
            path.push_back(root->val); //將當(dāng)前節(jié)點(diǎn)存入path
            dfs(root->left); //遍歷左子樹
            dfs(root->right); //遍歷右子樹
            path.pop_back(); //左右子樹遍歷完成后 這個(gè)根節(jié)點(diǎn)用完了 彈出
            return; //終止遞歸
        }
    }
    int count(vector<int> vec){ //將vec轉(zhuǎn)換為數(shù)字
        int sum = 0;
        int power = 1;
        for(int i=vec.size()-1;i>=0;i--){
            sum += power*vec[i];
            power *=10;
        }
        return sum;
    }
};

體會(huì)

這個(gè)題目與113比較類似。
都是遍歷樹，記錄下來路徑。這個(gè)題遍歷到葉節(jié)點(diǎn)之后，將記錄的路徑轉(zhuǎn)換和數(shù)字，將所有路徑的數(shù)字進(jìn)行求和，最終輸出整個(gè)樹的數(shù)字和。

LeetCode124 二叉樹中的最大路徑和

題目

給定一個(gè)非空二叉樹，返回其最大路徑和。

本題中，路徑被定義為一條從樹中任意節(jié)點(diǎn)出發(fā)，達(dá)到任意節(jié)點(diǎn)的序列。該路徑至少包含一個(gè)節(jié)點(diǎn)，且不一定經(jīng)過根節(jié)點(diǎn)。

示例 1:

輸入: [1,2,3]

       1
      / \
     2   3

輸出: 6

示例 2:

輸入: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

輸出: 42

C++代碼

class Solution {
public:
    int Max;
    int maxPathSum(TreeNode* root) {
        if(root == NULL) return 0; //根節(jié)點(diǎn)為空 直接返回
        Max = INT_MIN; //將MAX初始化為一個(gè)極小的值
        dfs(root); //dfs
        return Max; //返回最大值
    }
    
    int dfs(TreeNode* root){
        if(root==NULL) return 0; //節(jié)點(diǎn)為NULL 直接返回
        int left = dfs(root->left); //遍歷左子樹
        int right = dfs(root->right); //遍歷右子樹
        Max = max(Max,root->val+max(0,left)+max(0,right)); //計(jì)算當(dāng)前的Max Max為左子樹最大路徑的值 + 右子樹最大路徑的值 + 根節(jié)點(diǎn)的值
        return max(0,max(left,right))+root->val; //返回 左子樹 或者 右子樹 中最大不分叉路徑的值。
    }
};

體會(huì)

這個(gè)題被劃分到了困難題，其實(shí)還是有一些巧妙的。
首先我們觀察一下題目中給的樣例，不能發(fā)現(xiàn)。這個(gè)題不能夠用之前我們寫的求根節(jié)點(diǎn)到任意葉節(jié)點(diǎn)的路徑和的思路去解答。因?yàn)樽畲笾岛芸赡苁侨~節(jié)點(diǎn)到葉節(jié)點(diǎn)的。
這個(gè)題我們需要設(shè)定一個(gè)MAX作為最后的結(jié)果，遍歷節(jié)點(diǎn)的左子樹和右子樹，將左子樹的最大不分叉路徑（大于0）+ 右子樹的最大不分叉路徑（大于0）+ 節(jié)點(diǎn)本身的值與當(dāng)前最大路徑和Max作比較，將較大的數(shù)保存于MAX。dfs返回的是左子樹或者右子樹最大不分叉路徑的值，最終結(jié)果返回MAX即可。
建議手動(dòng)調(diào)試一遍，理解更深入。

LeetCode130 被圍繞的區(qū)域

題目

給定一個(gè)二維的矩陣，包含 'X' 和 'O'（字母 O）。

找到所有被 'X' 圍繞的區(qū)域，并將這些區(qū)域里所有的 'O' 用 'X' 填充。

示例:

X X X X
X O O X
X X O X
X O X X

運(yùn)行你的函數(shù)后，矩陣變?yōu)椋?/p> 

X X X X
X X X X
X X X X
X O X X

解釋:

被圍繞的區(qū)間不會(huì)存在于邊界上，換句話說，任何邊界上的 'O' 都不會(huì)被填充為 'X'。 任何不在邊界上，或不與邊界上的 'O' 相連的 'O' 最終都會(huì)被填充為 'X'。如果兩個(gè)元素在水平或垂直方向相鄰，則稱它們是“相連”的。

C++代碼

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if(board.size()==0) return ;
        //遍歷第一行與最后一行
        for(int i=0;i<board[0].size();i++){
            dfs(board,0,i);
            dfs(board,board.size()-1,i);
        }         
        //遍歷第一列與最后一列
        for(int i=0;i<board.size();i++){
            dfs(board,i,0);                
            dfs(board,i,board[0].size()-1);
        }
        //將所有標(biāo)為A的地方填充為O，剩下的為X
        for(int i=0;i<board.size();i++){
            for(int j=0;j<board[0].size();j++){
                if(board[i][j]=='A') board[i][j]='O';
                else board[i][j]='X';
            }
        }
    }
    void dfs(vector<vector<char>>& board,int x,int y){
        //注意，先判定邊界，再進(jìn)行訪問，不然可能會(huì)出現(xiàn)數(shù)組越界的情況
        if(x<board.size() && x>=0 && y<board[0].size() &&y>=0 && board[x][y]=='O'){
            board[x][y]='A';
            dfs(board,x-1,y);
            dfs(board,x+1,y);
            dfs(board,x,y-1);
            dfs(board,x,y+1);
        }
        return;
    }
};

體會(huì)

看到這個(gè)題，我們首先會(huì)想到，遍歷數(shù)組，對(duì)每一個(gè)O做連通區(qū)域的判斷。但是這樣做非常麻煩。我們可以轉(zhuǎn)換一下思路，遍歷邊緣的點(diǎn)，如果是O的話，將它所聯(lián)通的區(qū)域標(biāo)為A。最后將所有為A的點(diǎn)標(biāo)為O，剩下的點(diǎn)全是X。

LeetCode114 二叉樹展開為鏈表

題目

給定一個(gè)二叉樹，原地將它展開為鏈表。

例如，給定二叉樹

    1
   / \
  2   5
 / \   \
3   4   6

將其展開為：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

C++代碼

class Solution {
public:
    void flatten(TreeNode* root) {
        dfs(root);
        l2r_reverse(root);
    }
    void dfs(TreeNode* root){
        if(isLeaf(root) || root==NULL) return;
        else {
            dfs(root->left);
            dfs(root->right);
            move(root);
        }
    }
    //判斷一個(gè)節(jié)點(diǎn)是否是葉節(jié)點(diǎn)
    bool isLeaf(TreeNode* root){
        if(!root) return false;
        if(root->left==NULL && root->right==NULL) return true;
        else return false;
    }
    //將該節(jié)點(diǎn)右子樹的所有內(nèi)容全部放到左子樹最后一個(gè)節(jié)點(diǎn)的下面
    void move(TreeNode* root){
        //如果有左子樹找 到左子樹的最后一個(gè)節(jié)點(diǎn)
        if(root->left!=NULL) {
            TreeNode *tmp = root->left;
            while (tmp->left) {
                tmp = tmp->left;
            }
            tmp->left = root->right;
            root->right = NULL;
        }
        else{ //如果左子樹不存在，直接將右子樹的變?yōu)樽笞訕?            root->left = root->right;
            root->right = NULL;
        }
    }
    //將單線的左子樹 完全 變?yōu)橛易訕?    void l2r_reverse(TreeNode* root){
        if(!root)
            return;
        l2r_reverse(root->left);
        if(root->left!=NULL &&root->right==NULL){
            root->right = root->left;
            root->left = NULL;
            return;
        }
    }
};

體會(huì)

這個(gè)題比較有趣。我采用的方法是（雖然我感覺我搞復(fù)雜了）從下開始，將每一個(gè)父節(jié)點(diǎn)的右子樹放到左子樹最后一個(gè)節(jié)點(diǎn)下面。通過這個(gè)方法最后會(huì)得到一個(gè)向左偏的單鏈表，我們?cè)賹⑦@個(gè)樹旋轉(zhuǎn)為向右偏，得到最后的鏈表。

LeetCode116 填充同一層的兄弟節(jié)點(diǎn)

題目

給定一個(gè)二叉樹

struct TreeLinkNode {
  TreeLinkNode *left;
  TreeLinkNode *right;
  TreeLinkNode *next;
}

填充它的每個(gè) next 指針，讓這個(gè)指針指向其下一個(gè)右側(cè)節(jié)點(diǎn)。如果找不到下一個(gè)右側(cè)節(jié)點(diǎn)，則將 next 指針設(shè)置為 NULL。

初始狀態(tài)下，所有 next 指針都被設(shè)置為 NULL。

說明:

你只能使用額外常數(shù)空間。
使用遞歸解題也符合要求，本題中遞歸程序占用的?？臻g不算做額外的空間復(fù)雜度。
你可以假設(shè)它是一個(gè)完美二叉樹（即所有葉子節(jié)點(diǎn)都在同一層，每個(gè)父節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)）。
示例:

給定完美二叉樹，

     1
   /  \
  2    3
 / \  / \
4  5  6  7

調(diào)用你的函數(shù)后，該完美二叉樹變?yōu)椋?/p> 

     1 -> NULL
   /  \
  2 -> 3 -> NULL
 / \  / \
4->5->6->7 -> NULL

C++代碼

class Solution {
public:
    void connect(TreeLinkNode *root) {
        dfs(root);
    }
    void dfs(TreeLinkNode* root){
        if(!root) return;//如果節(jié)點(diǎn)為空就返回
        if(root->left && root->right){ //如果節(jié)點(diǎn)的左右節(jié)點(diǎn)都存在（題目已經(jīng)說了都存在 不判斷也可以）
            root->left->next = root->right; //直接連接
            if(root->next) root->right->next = root->next->left; //這個(gè)是用來連接5和6的
            else root->right->next = NULL;//這個(gè)是用來連接7與NULL
        }
        dfs(root->left);//遞歸
        dfs(root->right);//遞歸
    }
};

體會(huì)

這個(gè)題目比較簡(jiǎn)單，直接模擬這個(gè)過程就可以，代碼也比較短。

LeetCode117 填充同一層的兄弟節(jié)點(diǎn) II

題目

給定一個(gè)二叉樹

struct TreeLinkNode {
  TreeLinkNode *left;
  TreeLinkNode *right;
  TreeLinkNode *next;
}

填充它的每個(gè) next 指針，讓這個(gè)指針指向其下一個(gè)右側(cè)節(jié)點(diǎn)。如果找不到下一個(gè)右側(cè)節(jié)點(diǎn)，則將 next 指針設(shè)置為 NULL。

初始狀態(tài)下，所有 next 指針都被設(shè)置為 NULL。

說明:

你只能使用額外常數(shù)空間。
使用遞歸解題也符合要求，本題中遞歸程序占用的?？臻g不算做額外的空間復(fù)雜度。
示例:

給定二叉樹，

     1
   /  \
  2    3
 / \    \
4   5    7

調(diào)用你的函數(shù)后，該二叉樹變?yōu)椋?/p> 

     1 -> NULL
   /  \
  2 -> 3 -> NULL
 / \    \
4-> 5 -> 7 -> NULL

C++代碼

class Solution {
public:
    void connect(TreeLinkNode *root) {
        //start用于連接兩個(gè)層，其next為下一個(gè)層的首元素
        //tmp用來遍歷整個(gè)樹
        //tmp始終比root低一層
        TreeLinkNode * start = new TreeLinkNode(0);
        TreeLinkNode * tmp = start; //tmp指向start （很重要，用來連接下一層）
        while(root){
            //如果根節(jié)點(diǎn)存在左節(jié)點(diǎn)，tmp與根節(jié)點(diǎn)的左節(jié)點(diǎn)連接 修改tmp到同層下一個(gè)節(jié)點(diǎn) 對(duì)一個(gè)每一層第一個(gè)元素，這個(gè)步驟完成了start與下層第一個(gè)元素的連接
            if(root->left){
                tmp->next = root->left;
                tmp = tmp->next;
            }
            //如果根節(jié)點(diǎn)存在右節(jié)點(diǎn)，tmp與根節(jié)點(diǎn)的右節(jié)點(diǎn)連接，修改tmp到同層下一個(gè)節(jié)點(diǎn)
            if(root->right){
                tmp->next = root->right;
                tmp = tmp->next;
            }
            root = root->next;//root向同層下一個(gè)節(jié)點(diǎn)移動(dòng)
            //如果root不存在，證明這一層遍歷完了，我們修改root 變?yōu)橄乱粚拥谝粋€(gè)節(jié)點(diǎn)，修改start后為NULL，tmp重新指向start（很重要，用來連接下一層）
            if(!root){
                root = start->next;
                start->next = NULL;
                tmp = start;
            }
        }
    }
};

體會(huì)

這個(gè)題是116的通常形式。說實(shí)話，這個(gè)題寫了很久，最后還是錯(cuò)了?？戳司W(wǎng)上的同解，覺得寫的很巧妙。網(wǎng)上的代碼基本沒有注釋，我在這里把注釋補(bǔ)全，方便大家。強(qiáng)烈建議自己手動(dòng)調(diào)試一遍。

附錄

對(duì)于116 117所給出的代碼，LeetCode上面沒有給出調(diào)試的環(huán)境，和所依賴的函數(shù)。
我根據(jù)之前建樹的代碼寫了一份116 117，TreeLinkNode 的根據(jù)字符串建樹的代碼，下面放到這里，大家自取。

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <sstream>
using namespace std;
struct TreeLinkNode {
    int val;
    TreeLinkNode *left, *right, *next;
    TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
};
void trimLeftTrailingSpaces(string &input) {
    input.erase(input.begin(), find_if(input.begin(), input.end(), [](int ch) {
        return !isspace(ch);
    }));
}

void trimRightTrailingSpaces(string &input) {
    input.erase(find_if(input.rbegin(), input.rend(), [](int ch) {
        return !isspace(ch);
    }).base(), input.end());
}

TreeLinkNode* stringToTreeNode(string input) {
    trimLeftTrailingSpaces(input);
    trimRightTrailingSpaces(input);
    input = input.substr(1, input.length() - 2);
    if (!input.size()) {
        return nullptr;
    }

    string item;
    stringstream ss;
    ss.str(input);

    getline(ss, item, ',');
    TreeLinkNode* root = new TreeLinkNode(stoi(item));
    queue<TreeLinkNode*> nodeQueue;
    nodeQueue.push(root);

    while (true) {
        TreeLinkNode* node = nodeQueue.front();
        nodeQueue.pop();

        if (!getline(ss, item, ',')) {
            break;
        }

        trimLeftTrailingSpaces(item);
        if (item != "null") {
            int leftNumber = stoi(item);
            node->left = new TreeLinkNode(leftNumber);
            nodeQueue.push(node->left);
        }


        if (!getline(ss, item, ',')) {
            break;
        }

        trimLeftTrailingSpaces(item);
        if (item != "null") {
            int rightNumber = stoi(item);
            node->right = new TreeLinkNode(rightNumber);
            nodeQueue.push(node->right);
        }
    }
    return root;
}

int main(){
    TreeLinkNode * root;
    root = stringToTreeNode("{2,1,3,0,7,9,1,2,null,1,0,null,null,8,8,null,null,null,null,7}");
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 題量有點(diǎn)多，建議Ctrl + F題號(hào)或題目哦~ 二叉樹的遍歷（前序遍歷，中序遍歷，后序遍歷）[144] Binar...
    野狗子嗷嗷嗷閱讀 9,334評(píng)論 2贊 37
  • 樹的概述 樹是一種非常常用的數(shù)據(jù)結(jié)構(gòu)，樹與前面介紹的線性表，棧，隊(duì)列等線性結(jié)構(gòu)不同，樹是一種非線性結(jié)構(gòu) 1.樹的定...
    Jack921閱讀 4,750評(píng)論 1贊 31
  • 上一篇文章講述了樹的概念， 特征以及分類， 旨在讓我們理解什么是樹， 樹的一些常用的概念是什么，樹的分類有哪些等。...
    DevCW閱讀 2,224評(píng)論 4贊 10
  • 一些概念 數(shù)據(jù)結(jié)構(gòu)就是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及它們之間相互關(guān)系，并對(duì)這種結(jié)構(gòu)定義相應(yīng)的運(yùn)算，而且確保經(jīng)過這...
    Winterfell_Z閱讀 6,573評(píng)論 0贊 13
  • 文／07 梅泣春早殘雪消 傲骨凌寒獨(dú)自潮 難舍風(fēng)花雪夜靜 一陣風(fēng)來襲春騷 幽谷蘭馨送梅落 溪水解凍涌入河 一夜春風(fēng)...
    723edf844d12閱讀 475評(píng)論 15贊 26

友情鏈接更多精彩內(nèi)容