二叉树中序非递归遍历

  

   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       * 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 {
     
    
   

    

     

    
    

     

      public:
     
    
   

    

     

    
    

     

          vector<int> inorderTraversal(TreeNode* root) {
     
    
   

    

     

    
    

     

              stack<TreeNode*> stk;
     
    
   

    

     

    
    

     

              vector<int> out;
     
    
   

    

     

    
    

     

              TreeNode *tmp=root;
     
    
   

    

     

    
    

     

              if(!root) return out;
     
    
   

    

     

    
    

     

              while(!stk.empty()||tmp!=NULL){
     
    
   

    

     

    
    

     

                  if(tmp){
     
    
   

    

     

    
    

     

                      stk.push(tmp);
     
    
   

    

     

    
    

     

                      tmp=tmp->left;
     
    
   

    

     

    
    

     

                  }else{
     
    
   

    

     

    
    

     

                      tmp=stk.top();
     
    
   

    

     

    
    

     

                      stk.pop();
     
    
   

    

     

    
    

     

                      out.push_back(tmp->val);
     
    
   

    

     

    
    

     

                      tmp=tmp->right;
     
    
   

    

     

    
    

     

                  }
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

              return out;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      };
     
    
   

    

     

    
    

     

      /*中序非递归遍历de算法思想:
     
    
   

    

     

    
    

     

      根据中序遍历的顺序，对于任意一个结点，优先访问左孩子，再继续访问该左孩子的左孩子，然直到遇到左孩子结点为空的结点才停止访问，然后按照相同规则访问右子树。处理过程如下：
     
    
   

    

     

    
    

     

      对于任意结点：
     
    
   

    

     

    
    

     

      a。若左孩子不空，将tmp入栈，并将tmp的左孩子设置为新的tmp,
     
    
   

    

     

    
    

     

      然后对当前的结点进行相同的操作;
     
    
   

    

     

    
    

     

      b。若其左孩子(tmp)为空，则取栈顶元素并进行出栈操作，访问该
     
    
   

    

     

    
    

     

      栈顶结点，然后对当前的tmp置为栈顶结点的右孩子
     
    
   

    

     

    
    

     

      c。直到tmp为空并且栈为空的，则while循环结束
     
    
   

    

     

    
    

     

      */
     
    
  
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/96473975