Binary Tree

中序遍历 (In-order)

leetcode

Recursion

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    if (root == NULL) return result;
    result = inorderTraversal(root->left);
    result.push_back(root->val);
    vector<int> right = inorderTraversal(root->right);
    for (auto i : right) result.push_back(i);
    return result;
}

Stack

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    if (root == nullptr) return result;
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
        if (s.top()->left != nullptr) s.push(s.top()->left);
        else {
            while (!s.empty()) {
                TreeNode* node = s.top();
                result.push_back(node->val);
                s.pop();
                if (node->right != nullptr) {
                    s.push(node->right);
                    break;
                }
            }
        }
    }
    return result;
}

下面这个写法感觉更简单些

就是同时维持一个ptr来帮助访问

vector<int> inorderTraversal(TreeNode *root) {
    stack<TreeNode*> s;
    vector<int> v;
    TreeNode *ptr = root;
    while (ptr != nullptr || !s.empty()) {
        while (ptr != nullptr) {
            s.push(ptr);
            ptr = ptr->left;
        }
        if (!s.empty()) {
            ptr = s.top();
            s.pop();
            v.push_back(ptr->val);
            ptr = ptr->right;
        }
    }
    return v;
}

Morris

只用O(1)空间复杂度

思路是从root出发，将一个节点的前继节点的右指针指向它

流程如下

1. 如果一个点左孩子为空，那么将这个节点输出，然后访问其右节点
2. 左孩子不为空，从左孩子开始一路向右，即访问当前节点的前继节点
   1. 如果前继节点右孩子为空，那么指向当前节点，然后访问当前节点左孩子
   2. 前继节点右孩子指向当前节点，说明左侧子树已经全部访问过，那么输出当前节点，然后访问当前节点的右孩子

算法时间复杂度为$O(N)$，因为每条边访问次数是常数，如修改前继节点的右孩子为两次，输出自己为一次，而二叉树边数目为$N-1$

vector<int> inorderTraversal(TreeNode* root) {
    TreeNode *node = root, *prev = nullptr;
    vector<int> v;
    while (node != nullptr) {
        if (node->left == nullptr) {
            v.push_back(node->val);
            node = node->right;
        } else {
            TreeNode *prev = node->left;
            while (prev->right != nullptr && prev->right != node) prev = prev->right;
            if (prev->right == nullptr) {
                prev->right = node;
                node = node->left;
            } else {
                prev->right = nullptr;
                v.push_back(node->val);
                node = node->right;
            }
        }
    }
    return v;
}

---

前序遍历 (Pre-order)

leetcode

Recursion

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> v;
    if (root == nullptr) return v;
    v.push_back(root->val);
    vector<int> l = preorderTraversal(root->left);
    for (auto n : l) v.push_back(n);
    vector<int> r = preorderTraversal(root->right);
    for (auto n : r) v.push_back(n);
    return v;
}

Stack

同样是这种写法，借助一个ptr后简单了很多，只需要记录一下之前入栈的元素，可以回溯即可

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> v;
    stack<TreeNode*> s;
    TreeNode *ptr = root;
    while (ptr != nullptr || !s.empty()) {
        while (ptr != nullptr) {
            v.push_back(ptr->val);
            s.push(ptr);
            ptr = ptr->left;
        }
        if (!s.empty()) {
            ptr = s.top();
            s.pop();
            ptr = ptr->right;
        }
    }
    return v;
}

这是一种更简单的写法

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> v;
    if (root == nullptr) return v;
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
        TreeNode *node = s.top();
        s.pop();
        v.push_back(node->val);
        if (node->right != nullptr) s.push(node->right);
        if (node->left != nullptr) s.push(node->left);
    }
    return v;
}

Morris

流程和in-order的morris一样，区别就在于第二个push_back(cur->val)的位置变一下

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> v;
    TreeNode *cur = root, *prev = nullptr;
    while (cur != nullptr) {
        if (cur->left == nullptr) {
            v.push_back(cur->val);
            cur = cur->right;
        } else {
            prev = cur->left;
            while (prev->right != nullptr && prev->right != cur) prev = prev->right;
            if (prev->right == nullptr) {
                prev->right = cur;
                v.push_back(cur->val);
                cur = cur->left;
            } else {
                prev->right = nullptr;
                cur = cur->right;
            }
        }
    }
    return v;
}

---

后序遍历 (Post-order)

leetcode

Recursion

vector<int> postorderTraversal(TreeNode* root) {
    if (root == nullptr) return {};
    vector<int> l = postorderTraversal(root->left);
    vector<int> r = postorderTraversal(root->right);
    for (auto n : r) l.push_back(n);
    l.push_back(root->val);
    return l;
}

Stack

后序遍历比较麻烦，因为要保证子节点都访问完了才行

这里用一个prev节点来记录前一个输出的节点，如果是当前节点的孩子节点则当前节点也可以输出

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> v;
    if (root == nullptr) return v;
    stack<TreeNode*> s;
    s.push(root);
    TreeNode *prev = root;
    while (!s.empty()) {
        TreeNode *ptr = s.top();
        if ((ptr->left == nullptr && ptr->right == nullptr) ||
           (ptr->right == nullptr && ptr->left == prev) ||
           (ptr->right == prev)) {
            v.push_back(ptr->val);
            s.pop();
            prev = ptr;
        } else {
            if (ptr->right != nullptr) s.push(ptr->right);
            if (ptr->left != nullptr) s.push(ptr->left);
        }
    }
    return v;
}

Morris

后序遍历morris流程还是和之前一样，区别在于

在第二次发现回环时，倒序进行输出

而这样从根节点开始一路向右的一列无法输出，在结束后专门进行输出

void reverse(TreeNode* begin, TreeNode* end) {
    if (begin == end) return;
    TreeNode *prev = nullptr, *cur = begin;
    while (prev != end) {
        TreeNode *next = cur->right;
        cur->right = prev;
        prev = cur;
        cur = next;
    }
}
vector<int> postorderTraversal(TreeNode* root) {
    vector<int> v;
    TreeNode *ptr = root;
    while (ptr != nullptr) {
        if (ptr->left == nullptr) ptr = ptr->right;
        else {
            TreeNode *prev = ptr->left;
            while (prev->right != nullptr && prev->right != ptr) prev = prev->right;
            if (prev->right == nullptr) {
                prev->right = ptr;
                ptr = ptr->left;
            } else {
                reverse(ptr->left, prev);
                for (TreeNode* temp = prev; temp != ptr->left; temp = temp->right)
                    v.push_back(temp->val);
                v.push_back(ptr->left->val);
                reverse(prev, ptr->left);
                prev->right = nullptr;
                ptr = ptr->right;
            }
        }
    }
    if (root != nullptr) {
        TreeNode* temp = root;
        while (temp->right != nullptr) temp = temp->right;
        reverse(root, temp);
        for (ptr = temp; ptr != root; ptr = ptr->right) v.push_back(ptr->val);
        v.push_back(root->val);
        reverse(temp, root);
    }
    return v;
}

---

层次遍历

BST

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int> > result;
    if (!root) return result;
    deque<TreeNode*> q;
    q.push_back(root);
    while (!q.empty()) {
        result.push_back(vector<int>());
        int size = q.size();
        while (size --) {
            TreeNode* node = q.front();
            if (node->left != NULL) q.push_back(node->left);
            if (node->right != NULL) q.push_back(node->right);
            q.pop_front();
            result.back().push_back(node->val);
        }
    }
    return result;
}

---

高度

leetcode

BST

int maxDepth(TreeNode* root) {
    if (root == NULL) return 0;
    deque<TreeNode*> q;
    q.push_back(root);
    int result = 0;
    while (!q.empty()) {
        result ++;
        int size = q.size();
        while (size --) {
            TreeNode* node = q.front();
            if (node->left != NULL) q.push_back(node->left);
            if (node->right != NULL) q.push_back(node->right);
            q.pop_front();
        }
    }
    return result;
}

Morris

思路就是维持一个depth变量，然后在第一次将前继叶子节点指回去的时候，就可以得到高度

同时在第二次进入循环后，要把高度减会到原来的值

以及，因为这样只有在路径包含左节点时才能计算出高度，因此需要单独计算一下最右边的路径长度，然后返回较大值

int maxDepth(TreeNode* root) {
    if (root == nullptr) return 0;
    int mx = 1, depth = 1;
    for (TreeNode *cur = root, *prev = nullptr; cur != nullptr ;) {
        if (cur->left == nullptr) {
            cur = cur->right;
            depth ++;
        } else {
            prev = cur->left;
            int temp = 1;
            while (prev->right != nullptr && prev->right != cur) {
                prev = prev->right;
                temp ++;
            }
            if (prev->right == nullptr) {
                prev->right = cur;
                cur = cur->left;
                mx = max(mx, temp + depth ++);
            } else {
                prev->right = NULL;
                depth = depth - temp;
                cur = cur->right;
            }
        }
    }
    int rightPath = 0;
    for (TreeNode *ptr = root; ptr != nullptr; ptr = ptr->right) rightPath ++;
    return max(mx, rightPath);
}