二叉樹的中序周遊（leetcode94）

名詞解釋

preorder: root-left-right

inorder: left-root-right

postorder: left-right-root

官方解法：https://leetcode.com/articles/binary-tree-inorder-traversal/#

線索二叉樹：https://www.cnblogs.com/guweiwei/p/7090050.html

wikipedia https://en.wikipedia.org/wiki/Threaded_binary_tree

“A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node (if it exists), and all left child pointers that would normally be null point to the inorder predecessor of the node.”[1]

思路

簡單dfs

通過stack用iteration代替recursive

mirror方法

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) {
        TreeNode * cur = root;
        stack<TreeNode * > st;
        vector<int> ans;
        if(!root)return ans;
        while(!st.empty() || cur)
        {
            while(cur)
            {
               
                st.push(cur);
                cur = cur -> left;
            }
            cur = st.top();
            st.pop();
            ans.push_back(cur -> val);
            cur = cur -> right;
        }
        return ans;
    }
};
           

mirro解法代碼

/* Function to traverse binary tree without recursion and
   without stack */
void MorrisTraversal(struct tNode *root)
{
  struct tNode *current,*pre;

  if(root == NULL)
     return; 

  current = root;
  while(current != NULL)
  {
    if(current->left == NULL)
    {
      printf(" %d ", current->data);
      current = current->right;
    }
    else
    {
      /* Find the inorder predecessor of current */
      pre = current->left;
      while(pre->right != NULL && pre->right != current)
        pre = pre->right;

      /* Make current as right child of its inorder predecessor */
      if(pre->right == NULL)
      {
        pre->right = current;
        current = current->left;
      }

     // MAGIC OF RESTORING the Tree happens here: 
      /* Revert the changes made in if part to restore the original
        tree i.e., fix the right child of predecssor */
      else
      {
        pre->right = NULL;
        printf(" %d ",current->data);
        current = current->right;
      } /* End of if condition pre->right == NULL */
    } /* End of if condition current->left == NULL*/
  } /* End of while */
}