一. 二叉树的遍历

二叉树的遍历是指按某条搜索路径访问树中每个结点，使得每个结点均被访问一次，而且仅被访问一次

1.1 先序遍历

1、访问根节点

2、先序遍历左子树

3、先序遍历右子树

递归算法

#include <vector>                                                                                                                                       
#include <cstdio>

void show(const std::vector<int> &vec){
    printf("%c", '{'); 
    for(int i = 0; i < vec.size(); ++i){
        if(i != vec.size() - 1)
            printf("%d, ", vec[i]);
        else    
            printf("%d}\n", vec[i]);
    }
}

void preOrder(const alice::TreeNode *root, std::vector<int> &order){
    if(root == nullptr)
        return;
    order.emplace_back(root->data);
    preOrder(root->lchild, order);
    preOrder(root->rchild, order);
}

int main(void){
    std::vector<int> data = {1, 2, 3, 4, 5};
    std::vector<int> index  = {0, 1, 1, 1, 1, 1};
    alice::Tree tree(data, index);
     
    std::vector<int> order;
    preOrder(tree.getRoot(), order);
    show(order);
    return 0;
}

非递归算法

void preOrder(alice::TreeNode *root, std::vector<int> &order){
    if(root == nullptr)
        return;
    std::stack<alice::TreeNode *> stack;
    stack.push(root);
    while(! stack.empty()){
        alice::TreeNode *top_node = stack.top();
        stack.pop();
        order.emplace_back(top_node->data);
        if(top_node->rchild)
            stack.push(top_node->rchild);
        if(top_node->lchild)
            stack.push(top_node->lchild);
    }
}

1.2 中序遍历

1、中序遍历左子树

2、访问根节点

3、中序遍历右子树

递归算法

void inOrder(alice::TreeNode *root, std::vector<int> &order){
    if(root == nullptr)
        return;
    inOrder(root->lchild, order);
    order.emplace_back(root->data);
    inOrder(root->rchild, order);
}

非递归算法

void inOrder(alice::TreeNode *root, std::vector<int> &order){
    if(root == nullptr)
        return;
    std::stack<alice::TreeNode *> stack;
    alice::TreeNode *cur_node = root;
    while(cur_node || ! stack.empty()){
        if(cur_node){
            stack.push(cur_node);
            cur_node = cur_node->lchild;
        }
        else{
            cur_node = stack.top();
            stack.pop();
            order.push_back(cur_node->data);
            cur_node = cur_node->rchild;
        }
    }
}

1.3 后序遍历

1、后序遍历左子树

2、后序遍历右子树

3、访问根节点

递归算法

void postOrder(alice::TreeNode *root, std::vector<int> &order){
    if(root == nullptr)
        return;
    postOrder(root->lchild, order);
    postOrder(root->rchild, order);
    order.emplace_back(root->data);
}

非递归算法，后序遍历是 “左右中”，因此我们只需将前序遍历转化为 “中右左”，再反转一下就可以了

void postOrder(alice::TreeNode *root, std::vector<int> &order){
    if(root == nullptr)
        return;
    std::stack<alice::TreeNode *> stack;
    stack.push(root);
    while(! stack.empty()){
        alice::TreeNode *top_node = stack.top();
        stack.pop();
        order.emplace_back(top_node->data);
        if(top_node->lchild)
            stack.push(top_node->lchild);
        if(top_node->rchild)
            stack.push(top_node->rchild);
    }
    std::reverse(order.begin(), order.end());
}

1.4 层次遍历

要进行层次遍历，需要借助一个队列。先将二叉树根节点入队，然后出队，访问出队结点，若它有左子树，则将左子树根节点入队；若它有右子树，则将右子树根节点入队。然后出队，访问出队结点 … 如何反复，直至队列为空

void levelOrder(alice::TreeNode *root, std::vector<int> &order){
    if(root == nullptr)
        return;
    std::queue<alice::TreeNode *> queue;
    queue.push(root);
    while(! queue.empty()){
        alice::TreeNode *front_node = queue.front();
        queue.pop();
        order.emplace_back(front_node->data);
        if(front_node->lchild)
            queue.push(front_node->lchild);
        if(front_node->rchild)
            queue.push(front_node->rchild);
    }
}

二. 二叉树

2.1 反转二叉树

递归算法

void reverse(alice::TreeNode *root){
    if(root == nullptr)
        return;
    std::swap(root->lchild, root->rchild);
    reverse(root->lchild);
    reverse(root->rchild);
}

非递归算法

void reverse(alice::TreeNode *root){
    if(root == nullptr)
        return;
    std::stack<alice::TreeNode *> stack;
    stack.push(root);
    while(! stack.empty()){
        alice::TreeNode *top_node = stack.top();
        stack.pop();
        std::swap(top_node->lchild, top_node->rchild);
        if(top_node->rchild)
            stack.push(top_node->rchild);
        if(top_node->lchild)
            stack.push(top_node->lchild);
    }
}

2.2 对称二叉树

递归算法

bool isSymmetric(alice::TreeNode *root){
    if(root == nullptr)
        return true;
    auto inner = [](const auto &inner, alice::TreeNode *lchild, alice::TreeNode *rchild) -> bool{
        if(lchild == nullptr && rchild != nullptr)
            return false;
        else if(lchild != nullptr && rchild == nullptr)
            return false;
        else if(lchild == nullptr && rchild == nullptr)
            return true;
        else if(lchild->data != rchild->data)
            return false;
        else
            return inner(inner, lchild->lchild, rchild->rchild) && inner(inner, lchild->rchild, rchild->lchild);
    };
    return inner(inner, root->lchild, root->rchild);
}

非递归算法

bool isSymmetric(alice::TreeNode *root){
    if(root == nullptr)
        return true;
    std::queue<alice::TreeNode *> queue;
    queue.push(root->lchild);
    queue.push(root->rchild);
    while(! queue.empty()){
        alice::TreeNode *node_1 = queue.front();
        queue.pop();
        alice::TreeNode *node_2 = queue.front();
        queue.pop();
        if(! node_1 && ! node_2)
            return true;
        else if(! node_1 || ! node_2 || node_1->data != node_2->data)
            return false;
        else{
            queue.push(node_1->lchild);
            queue.push(node_2->rchild);
            queue.push(node_1->rchild);
            queue.push(node_2->lchild);
        }
    }
    return true;
}

作业

实现对称二叉树的非递归算法