成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

leetcode講解--94. Binary Tree Inorder Traversal

henry14 / 2929人閱讀

摘要：題目地址嗯，經(jīng)典的題目，中序遍歷二叉樹(shù)。代碼如下中序遍歷先序遍歷后序遍歷是不是簡(jiǎn)單的不要不要的，遞歸就是這么美。右孩子后壓棧全部釋放出來(lái)嗯，總的來(lái)說(shuō)用迭代遍歷確實(shí)燒腦，沒(méi)什么性能上的特殊需求還是用遞歸寫法吧，對(duì)程序員友好哦。

94. Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes" values.

For example:
Given binary tree [1,null,2,3],
1

 2
/

3
return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

題目地址

嗯，經(jīng)典的題目，中序遍歷二叉樹(shù)。題目說(shuō)遞歸做起來(lái)太簡(jiǎn)單，請(qǐng)用迭代。我覺(jué)得還是先用遞歸做一下吧，也許我遞歸都不會(huì)呢？誰(shuí)知道呢，是吧。然后發(fā)現(xiàn)，嗯，果然很簡(jiǎn)單，我好像已經(jīng)不是從前那個(gè)菜逼了。

代碼如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
        vector vec;
public:
    vector inorderTraversal(TreeNode* root) {//中序遍歷
        if(root){
            inorderTraversal(root->left);
            vec.push_back(root->val);
            inorderTraversal(root->right);
        }
        return vec;
    }
    vector preorderTraversal(TreeNode* root){//先序遍歷
      if(root){
        vec.push_back(root->val);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
      }
      return vec;
    }
    vector postorderTraversal(TreeNode* root){//后序遍歷
      if(root){
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        vec.push_back(root->val);
      }
      return vec;
    }
};

是不是簡(jiǎn)單的不要不要的，遞歸就是這么美。

好了，現(xiàn)在想想怎么用迭代中序遍歷呢。別想了，用棧吧，不用棧你做給我看試試。

層次遍歷樹(shù)相當(dāng)于圖的廣度優(yōu)先遍歷(BFS,breadth first search)，先序、中序、后序遍歷二叉樹(shù)都相當(dāng)于圖的深度優(yōu)先遍歷(DFS,depth first search)。要用迭代可以啊，廣度優(yōu)先請(qǐng)用隊(duì)列，深度優(yōu)先請(qǐng)用棧。

借助棧深度優(yōu)先遍歷時(shí)，首先我們壓棧第一個(gè)結(jié)點(diǎn)（入口結(jié)點(diǎn)），然后又pop棧頂結(jié)點(diǎn)，我們把pop出來(lái)的結(jié)點(diǎn)的所有子節(jié)點(diǎn)都?jí)哼M(jìn)棧中，然后又是pop棧頂，繼續(xù)進(jìn)行如上操作。也許你發(fā)現(xiàn)了一個(gè)問(wèn)題：沒(méi)有說(shuō)哪個(gè)孩子先壓進(jìn)棧，哪個(gè)后壓棧，但有一點(diǎn)很明顯，先壓棧的會(huì)靠后訪問(wèn)，后壓棧的會(huì)先被訪問(wèn)。

上代碼：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    vector vec;
    stack s;
    stack s1;
public:
    vector inorderTraversal(TreeNode* root) {//中序遍歷
        TreeNode* current=root;
        while(!s.empty() || current!=NULL){
            while(current){//如果結(jié)點(diǎn)存在，則入棧，然后判斷左孩子
                s.push(current);//越靠近root的越先壓棧哦
                current = current->left;
            }
            //往左走到了盡頭，然后就是pop棧頂了
            current = s.top();
            s.pop();
            vec.push_back(current->val);
            //接著是判斷右孩子
            current = current->right;
        }
        return vec;
    }
    vector preorderTraversal(TreeNode* root){//先序遍歷
      TreeNode* current=root;
      while(!s.empty() || current!=NULL){
        while(current){
          vec.push_back(current->val);//遇到一個(gè)就先訪問(wèn)一個(gè)唄
          s.push(current->right);//右孩子壓棧，越靠近root的越先壓棧哦
          current = current->left;
        }
        current=s.top();
        s.pop();
      }
      return vec;
    }
    //后序遍歷，后序遍歷就有點(diǎn)復(fù)雜了，需要兩個(gè)棧，蛋疼。。。，
    //什么你問(wèn)我為啥多了一個(gè)棧，因?yàn)楦?jié)點(diǎn)要存起來(lái)啊，它非得要最后訪問(wèn)，就把它一腳踢進(jìn)棧里。
    vector postorderTraversal(TreeNode* root){
      TreeNode* current=root;
      s.push(current);
      while(!s.empty()){
          current = s.top();
          s.pop();
          s1.push(current);//s1就是用來(lái)放后序遍歷中的根結(jié)點(diǎn)的，root被壓到最底下了，哈哈。s1放的是逆序打印順序哦
          if(current->left)
            s.push(current->left);//左孩子先壓棧，先壓棧的后訪問(wèn)吶，左孩子不是應(yīng)該先訪問(wèn)嗎，拜托，后面要壓入s1，順序又反了。。
          if(current->right)
            s.push(current->right);//右孩子后壓棧
      }
      while(!s1.empty()){//全部釋放出來(lái)
        vec.push_back(s1.top()->val);
        s1.pop();
      }
      return vec;
    }
};

嗯，總的來(lái)說(shuō)用迭代遍歷確實(shí)燒腦，沒(méi)什么性能上的特殊需求還是用遞歸寫法吧，對(duì)程序員友好哦。

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/38361.html

相關(guān)文章

  • leetcode 94. Binary Tree Inorder Traversal

    摘要：題目要求中序遍歷樹(shù)，并將遍歷結(jié)果添加到數(shù)組中。分別用遞歸和循環(huán)的方式結(jié)局。如果當(dāng)前節(jié)點(diǎn)存在左子節(jié)點(diǎn)，則繼續(xù)遍歷左子樹(shù)直到最后一個(gè)左子節(jié)點(diǎn)。如果棧頂元素有右子節(jié)點(diǎn)，則將其右子節(jié)點(diǎn)壓入棧中作為，再繼續(xù)遍歷的左子節(jié)點(diǎn)。當(dāng)和都為空時(shí)，遍歷結(jié)束。 題目要求 Given a binary tree, return the inorder traversal of its nodes values....

    wpw 評(píng)論0 收藏0

  • LeetCode 之 JavaScript 解答第94題 —— 二叉樹(shù)的中序遍歷

    摘要：小鹿題目二叉樹(shù)中序遍歷給定一個(gè)二叉樹(shù)，返回它的中序遍歷。通常遞歸的方法解決二叉樹(shù)的遍歷最方便不過(guò)，但是我還是喜歡增加點(diǎn)難度，用一般的迭代循環(huán)來(lái)實(shí)現(xiàn)。 Time：2019/4/25Title:Binary Tree Inorder TraversalDifficulty: MediumAuthor:小鹿 題目：Binary Tree Inorder Traversal（二叉樹(shù)中序遍歷...

    Jason 評(píng)論0 收藏0

  • 94. Binary Tree Inorder Traversal

    摘要：題目解答合并兩個(gè)直接就好啦的方法很巧妙，當(dāng)時(shí)想了很久也沒(méi)做出來(lái)，所以這里標(biāo)注一下 題目：Given a binary tree, return the inorder traversal of its nodes values. For example:Given binary tree [1,null,2,3], 1 2 / 3 return ...

    dackel 評(píng)論0 收藏0

  • [Leetcode] Construct Binary Tree from Traversal 根據(jù)

    摘要：二分法復(fù)雜度時(shí)間空間思路我們先考察先序遍歷序列和中序遍歷序列的特點(diǎn)。對(duì)于中序遍歷序列，根在中間部分，從根的地方分割，前半部分是根的左子樹(shù)，后半部分是根的右子樹(shù)。 Construct Binary Tree from Preorder and Inorder Traversal Given preorder and inorder traversal of a tree, constru...

    caoym 評(píng)論0 收藏0

  • [LintCode/LeetCode] Binary Tree InOrder Traversal

    摘要：遞歸法不說(shuō)了，棧迭代的函數(shù)是利用的原理，從根節(jié)點(diǎn)到最底層的左子樹(shù)，依次入堆棧。然后將出的結(jié)點(diǎn)值存入數(shù)組，并對(duì)出的結(jié)點(diǎn)的右子樹(shù)用函數(shù)繼續(xù)迭代。 Problem Given a binary tree, return the inorder traversal of its nodes values. Example Given binary tree {1,#,2,3}, 1 ...

    tomorrowwu 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<