Morris Traversal(C++)


  • 0
    T

    Re: Morris Traversal------- NO RECURSION NO STACK

    /**

    • 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) {
      vector<int> res;
      if(root==NULL) return res;

       TreeNode* cur=root;
       TreeNode* prev;
       while(cur)
       {
            //左子树不存在,输出当前节点,并把当前节点更新为右子树
           if(cur->left==NULL)
           {
               res.push_back(cur->val);
               cur=cur->right;
           }
           else//左子树存在,找当前节点的前驱结点
           {
               prev=cur->left;
               while(prev->right&&prev->right!=cur)
               {
                   prev=prev->right;
               }
               
                 //前驱结点未被访问过将前驱结点的右指针域指向当前节点,当前节点更新为左子树
               if(prev->right==NULL)
               {
                   prev->right=cur;
                   cur=cur->left;
               }
               else//前驱结点已经被访问过,将前驱结点的右指针域恢复原来状态,输出当前值,并将当前节点更新为右子树
               {
                   prev->right==NULL;
                   res.push_back(cur->val);
                   cur=cur->right;
               }
           }
           
       }
       
       return res;
      

      }
      };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.