Binary tree traversal

Posted by chunyang on April 19, 2019

介绍

二叉树在面试过程中会经常遇到,经典问题是三种遍历方式中的一种(一般考查后续遍历,最难)。也会考查提 供两种遍历方式,用户用程序恢复二叉树。问题一般有递归和非递归方式(一般考查非递归,难一点)。本文介 绍三种问题的非递归解法,并且提供可以运行的程序。

三种遍历方式是:

  • 先序遍历:根节点,左子节点,右子节点
  • 中序遍历:左子节点,根节点,右子节点(二叉搜索树中生成有序数组)
  • 后续遍历:左子节点,右子节点,根节点

Preorder

基本数的定义,构造和打印

构造二叉树时,假定使用 ? 表示空节点,例如 1 ? 2 表示:

1
2

#include <deque>

#include <iostream>

#include <stack> // for  traversal

#include <string>

#include <vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v): val(v), left(NULL), right(NULL) {}
    static TreeNode* create_tree(string str);
    static string str(TreeNode* node);
    static void free_node(TreeNode* node);
};

TreeNode* TreeNode::create_tree(string str) {
    if (str.empty()) return NULL;
    int length = str.size();
    vector<TreeNode*> nodes;
    for(int i = 0; i < length; ++i) {
        int j = i;
        if (str[j] == ' ') continue;
        if (str[j] == '?') {
            nodes.push_back(NULL);
            continue;
        }
        while (j < length && str[j]>='0' && str[j] <= '9') ++j;
        cout << str.substr(i, j - i) << endl;
        nodes.push_back(new TreeNode(stoi(str.substr(i, j - i))));
        i = j;
    }
    length = nodes.size();
    for (int i = 0; i < length; ++i) {
        if (!nodes[i]) continue;
        cout << "connecting node: " << nodes[i]->val << endl;
        if (2 * i + 1 < length) nodes[i]->left = nodes[2 * i + 1];
        if (2 * i + 2 < length) nodes[i]->right = nodes[2 * i + 2];
    }
    cout << "nodes size: " << nodes.size() << endl;
    return nodes[0];
}

string TreeNode::str(TreeNode* node) {
    string s;
    if (!node) return s;
    deque<TreeNode*> cur;
    deque<TreeNode*> next;
    cur.push_back(node);
    int count = 1;
    while (!cur.empty()) {
        string cur_layer;
        int cur_count = 0;
        while (!cur.empty()) {
            TreeNode* node = cur.front(); cur.pop_front();
            ++cur_count;
            if (node == NULL) {
                cur_layer += "? ";
            }
            else {
                cout << "stringize node: " << node->val << endl;
                cur_layer += to_string(node->val);
                cur_layer += " ";
                if (node->left)
                    next.push_back(node->left);
                if (node->right)
                    next.push_back(node->right);
            }
        }
        int remain_q = count - cur_count;
        cout << "remain ?: " << remain_q << " cur layer: " << cur_layer << endl;
        while (remain_q-- > 0) s += "? ";
        count <<= 1;
        s += cur_layer;
        cur.swap(next);
    }
    int j = s.size();
    cout << "string s: " << s << endl;
    while (j > 0 && (s[j-1] == ' ' || s[j-1] == '?')) --j;
    return s.substr(0, j);
}


void TreeNode::free_node(TreeNode* node) {
    if (!node) return;
    if (node->left) free_node(node->left);
    if (node->right) free_node(node->right);
    delete node;
}

int main(int argc, char* argv[]) {

    string str = "1 ? 3 ? ? ? 5 ? ? ? ? ? ? 6 70";
    cout << "creating: " << str << endl;
    TreeNode* node = TreeNode::create_tree(str);
    cout << "string: " << TreeNode::str(node) << endl;
    TreeNode::free_node(node);

    return 0;
}

先序遍历

vector<int> preorder(TreeNode* node) {
    vector<int> result;
    stack<TreeNode*> st;
    st.push(node);
    while (!st.empty()) {
        TreeNode* top = st.top();
        result.push_back(top->val);
        if (top->right) st.push(top->right);
        if (top->left) st.push(top->left);
    }
    return result;
}

Inorder

vector<int> inorder(TreeNode* node) {
    vector<int> result;
    stack<TreeNode*> st;
    TreeNode* cur = node;
    while (!st.empty() || cur) {
        while (cur) {
            st.push(cur);
            cur = cur->left;
        }
        cur = st.top(); st.pop();
        result.push_back(cur->val);
        cur = cur->right;
    }

    return result;
}

Postorder

后续遍历时,我们需要避免重复遍历同一个节点。

vector<int> postorder(TreeNode* node) {
    vector<int> result;
    stack<TreeNode*> st;
    st.push(node);
    TreeNode* prev = NULL;
    while(!st.empty()) {
        TreeNode* top = st.top();
        if (prev != NULL && (prev == top->right || prev == top->left)) {
            result.push_back(top->val);
            st.pop();
            prev = top;
        } else if (top->left == NULL && top->right == NULL) {
            result.push_back(top->val);
            st.pop();
            prev = top;
        } else {
            if (top->right) st.push(top->right);
            if (top->left) st.push(top->left);
        }
    }



    return result;
}

State machine

Elements of programming 中,有另外一个非常巧妙的解法。利用状态机来完成转换。

重新建立依赖关系遍历

非递归一般需要使用栈来辅助。空间复杂度高。有一种方法重新建立关系,在遍历后恢复树来遍历。

本文完