leetcode講解--94. Binary Tree Inorder Traversal

henry14 發布于2019-07-25 11:22 / 2921人閱讀

摘要：題目地址嗯，經典的題目，中序遍歷二叉樹。代碼如下中序遍歷先序遍歷后序遍歷是不是簡單的不要不要的，遞歸就是這么美。右孩子后壓棧全部釋放出來嗯，總的來說用迭代遍歷確實燒腦，沒什么性能上的特殊需求還是用遞歸寫法吧，對程序員友好哦。

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?

題目地址

嗯，經典的題目，中序遍歷二叉樹。題目說遞歸做起來太簡單，請用迭代。我覺得還是先用遞歸做一下吧，也許我遞歸都不會呢？誰知道呢，是吧。然后發現，嗯，果然很簡單，我好像已經不是從前那個菜逼了。

代碼如下：

/**
 * 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;
    }
};

是不是簡單的不要不要的，遞歸就是這么美。

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

層次遍歷樹相當于圖的廣度優先遍歷(BFS,breadth first search)，先序、中序、后序遍歷二叉樹都相當于圖的深度優先遍歷(DFS,depth first search)。要用迭代可以啊，廣度優先請用隊列，深度優先請用棧。

借助棧深度優先遍歷時，首先我們壓棧第一個結點（入口結點），然后又pop棧頂結點，我們把pop出來的結點的所有子節點都壓進棧中，然后又是pop棧頂，繼續進行如上操作。也許你發現了一個問題：沒有說哪個孩子先壓進棧，哪個后壓棧，但有一點很明顯，先壓棧的會靠后訪問，后壓棧的會先被訪問。

上代碼：

/**
 * 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){//如果結點存在，則入棧，然后判斷左孩子
                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);//遇到一個就先訪問一個唄
          s.push(current->right);//右孩子壓棧，越靠近root的越先壓棧哦
          current = current->left;
        }
        current=s.top();
        s.pop();
      }
      return vec;
    }
    //后序遍歷，后序遍歷就有點復雜了，需要兩個棧，蛋疼。。。，
    //什么你問我為啥多了一個棧，因為根節點要存起來啊，它非得要最后訪問，就把它一腳踢進棧里。
    vector postorderTraversal(TreeNode* root){
      TreeNode* current=root;
      s.push(current);
      while(!s.empty()){
          current = s.top();
          s.pop();
          s1.push(current);//s1就是用來放后序遍歷中的根結點的，root被壓到最底下了，哈哈。s1放的是逆序打印順序哦
          if(current->left)
            s.push(current->left);//左孩子先壓棧，先壓棧的后訪問吶，左孩子不是應該先訪問嗎，拜托，后面要壓入s1，順序又反了。。
          if(current->right)
            s.push(current->right);//右孩子后壓棧
      }
      while(!s1.empty()){//全部釋放出來
        vec.push_back(s1.top()->val);
        s1.pop();
      }
      return vec;
    }
};

嗯，總的來說用迭代遍歷確實燒腦，沒什么性能上的特殊需求還是用遞歸寫法吧，對程序員友好哦。

云服務器 GPU云服務器 binary-tree binary-search-tree Inorder Traversal

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/38361.html

leetcode 94. Binary Tree Inorder Traversal

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

wpw 2019-08-15 10:54 評論0 收藏0
LeetCode 之 JavaScript 解答第94題 —— 二叉樹的中序遍歷

摘要：小鹿題目二叉樹中序遍歷給定一個二叉樹，返回它的中序遍歷。通常遞歸的方法解決二叉樹的遍歷最方便不過，但是我還是喜歡增加點難度，用一般的迭代循環來實現。 Time：2019/4/25Title:Binary Tree Inorder TraversalDifficulty: MediumAuthor:小鹿題目：Binary Tree Inorder Traversal（二叉樹中序遍歷...

Jason 2019-08-23 17:19 評論0 收藏0
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 ...

dackel 2019-08-14 14:12 評論0 收藏0
[Leetcode] Construct Binary Tree from Traversal 根據

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

caoym 2019-08-14 12:32 評論0 收藏0
[LintCode/LeetCode] Binary Tree InOrder Traversal

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

tomorrowwu 2019-08-14 15:39 評論0 收藏0