二叉树

树节点

struct TreeNode{
    int val;
    TreeNode * left, * right;
    TreeNode(int val){
        this->val = val;
        this->left=nullptr;
        this->right= nullptr;
    }
};

二叉树前中后序遍历递归非递归

// 递归实现
void pre_order(TreeNode * head){
    if(head==nullptr)
        return;
    cout<<head->val<<endl;
    if(head->left)
        pre_order(head->left);
    if(head->right)
        pre_order(head->right);
}

void in_order(TreeNode * head){
    if(head->left)
        in_order(head->left);
    cout<<head->val<<endl;
    if(head->right)
        in_order(head->right);
}

void post_order(TreeNode * head){
    if(head->left)
        post_order(head->left);
    if(head->right)
        post_order(head->right);
    cout<<head->val<<endl;

}

//非递归实现, 递归的本质是模拟栈, 因此非递归人工操作栈即可
void pre_order(TreeNode* tree){
    if(tree== nullptr)
        return;
    stack<TreeNode*> s;
    s.push(tree);
    while(!s.empty()){
        TreeNode* node = s.top();
        s.pop();
        cout<<node->val<<endl;
        if(node->right)
            s.push(node->right);
        if(node->left)
            s.push(node->left);
    }
}

void in_order(TreeNode* tree){
    if(tree== nullptr)
        return;
    stack<TreeNode*> s;
    while(tree){
        s.push(tree);
        tree=tree->left;
    }
    while (!s.empty()){
        TreeNode* node= s.top();
        cout<<node->val<<endl;
        s.pop();
        if(node->right){
            node=node->right;
            while(node){
                s.push(node);
                node=node->left;
            }
        }
    }
}

void post_order(TreeNode* tree){
    if(!tree)
        return;
    stack<TreeNode*> s;
    while(tree){
        s.push(tree);
        tree=tree->left;
    }
    TreeNode* pre= nullptr;
    while (!s.empty()){
        TreeNode* node=s.top();
        if(node->right && node->right!=pre){
            node=node->right;
            while (node){
                s.push(node);
                node=node->left;
            }
        } else{
        cout<<node->val<<endl;
        pre=node;
        s.pop();
        }
    }
}

前序、中序重构二叉树

TreeNode* constructCore(vector<int> pre_order, int p_low, int p_high, vector<int> in_order, int i_low, int i_high){
    int root_val = pre_order[p_low];
    TreeNode * root = new TreeNode(root_val);
    root->left=root->right= nullptr;

    if(p_low==p_high){
        return root;
    }

    int left_len = 0;
    while(left_len + i_low < i_high){
        if(in_order[i_low+left_len]==pre_order[p_low])
            break;
        left_len++;
    }
    if(left_len>0){
        root->left=constructCore(pre_order,p_low+1, p_low+ left_len, in_order, i_low, left_len-1);
    }
    if(left_len<i_high-i_low){
        root->right=constructCore(pre_order, p_low + left_len +1, p_high, in_order, left_len+1, i_high);
    }
    return root;
}

TreeNode* reconstruct_tree(vector<int> pre_order, vector<int> in_order){
    if(pre_order.size()!=in_order.size())
        return nullptr;
    return constructCore(pre_order, 0, pre_order.size()-1, in_order, 0, in_order.size()-1);
}

给定两棵二叉树, 判断一棵是否是另一棵的子树.

bool isSubTreeCore(TreeNode* root, TreeNode* sub){
    if(sub== nullptr)
        return true;
    if(root==nullptr)
        return false;
    if(root->val!=sub->val)
        return false;
    return isSubTreeCore(root->left, sub->left) && isSubTreeCore(root->right, sub->right);
}

bool isSubTree(TreeNode* root, TreeNode* sub){
    if(root== nullptr and sub== nullptr)
        return true;
    if(sub== nullptr)
        return true;
    stack<TreeNode*> s;
    s.push(root);
    while(!s.empty()){
        TreeNode* node= s.top();
        s.pop();
        if(node->val==sub->val && isSubTreeCore(node, sub))
            return true;
        s.push(node->left);
        s.push(node->right);
    }
    return false;
}

树的镜像

void mirrorTree(TreeNode* root){
    if(root== nullptr)
        return;
    TreeNode* temp = root->right;
    root->right=root->left;
    root->left=temp;
    mirrorTree(root->left);
    mirrorTree(root->right);
}

层次遍历二叉树

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if(root==NULL)
        return res;
    queue<TreeNode*> q;
    int level=1;
    int cur_nums=0;
    vector<int> temp;
    q.push(root);
    while(!q.empty()){
        TreeNode* node = q.front();
        temp.push_back(node->val);
        q.pop();
        if(node->left){
            q.push(node->left);
            cur_nums++;
        }
        if(node->right){
            q.push(node->right);
            cur_nums++;
        }
        level--;
        if(level==0){
            res.push_back(temp);
            temp.clear();
            level=cur_nums;
            cur_nums=0;
        }
    }
    return res;
}