aboutsummaryrefslogtreecommitdiff
path: root/binary_tree_preorder.cpp
blob: 7bba4353e1a758f286e23bcfeea5cd286e750dc8 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include "leetcode.h"

class Solution {
public:
  vector<int> preorderTraversal(TreeNode *root) {
    // morris traversal
    vector<int> nodes;
    while (root) {
      if (root->left) {
        TreeNode *pre = root->left;
        while (pre->right && pre->right != root)
          pre = pre->right;
        if (!pre->right) {
          pre->right = root;
          nodes.push_back(root->val);
          root = root->left;
        } else {
          pre->right = NULL;
          root = root->right;
        }
      } else {
        nodes.push_back(root->val);
        root = root->right;
      }
    }
    return nodes;
  }
};