leetcode讲解--94. Binary Tree Inorder Traversal

henry14 发布于2019-07-25 11:22 / 2923人阅读

摘要：题目地址嗯，经典的题目，中序遍历二叉树。代码如下中序遍历先序遍历后序遍历是不是简单的不要不要的，递归就是这么美。右孩子后压栈全部释放出来嗯，总的来说用迭代遍历确实烧脑，没什么性能上的特殊需求还是用递归写法吧，对程序员友好哦。

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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