二叉树

先序非递归

　　递归算法使用栈的特性——先进后出，因此非递归遍历二叉树时也需要用栈来模拟递归调用。递归处理内容如下：

当前节点的右子树若存在压栈
当前节点的左子树若存在压栈
当前节点再次压栈（以便下次非递归时访问）

　　非递归处理内容

访问当前节点
弹出当前节点

typedef struct TreeNode {
    int val;
    TreeNode *left, *right;
}TreeNode;

vector<int> preorderTraversal(TreeNode *root) {
    if(root == nullptr) {
        return {};
    }
    
    vector<int> res;
    stack<TreeNode *> call;
    call.push(root)
    while(!call.empty()) {
        TreeNode *tmp = call.top();
        call.pop();
        if(tmp != nullptr) { //当前节点没有被访问过 
            if(tmp->right) {
                call.push(tmp->right); //1.栈的最底层，最后处理右子树 
            }
            if(tmp->left) { //2.左子树在右子树上，因为先序遍历先访问左子树 
                call.push(tmp->left);
            }
            call.push(tmp); //3.当前访问的结点(可以看做根节点)在左子树上方，先序遍历根节点在左子树前被访问 
            call.push(nullptr); //4.标记当前结点被访问过 
        }
        else { //当前节点被访问过 
            res.push_back(call.top()->val); //5.访问当前节点，也就是加入结果集中 
            call.pop(); //6.彻底删除当前节点 
        }
    }
    return res;
}

中序非递归

　　栈低到栈顶的顺序为：右子树-根节点-左子树，下次递归时左子树要弹出标记为被访问的节点

vector<int> inorderTraversal(TreeNode *root) {
    if(root == nullptr) {
        return {};
    }
    
    vector<int> res;
    stack<TreeNode *> call;
    call.push(root);
    while(!call.empty()) {
        TreeNode *tmp = call.top();
        call.pop();
        if(tmp != nullptr) {
            if(tmp->right) {
                call.push(tmp->right);
            }
            call.push(tmp);
            call.push(nullptr);//标记为要访问的结点，待处理;当左右子树都不存在时当前节点就是最后一个访问的结点 
            if(tmp->left) {
                call.push(tmp->left); //沿着左子树一直往左下方走 
            }
        }
        else {
            res.push_back(call.top()->val);
            call.pop(); 
        }
    }
    return res;
}

后序非递归

vector<int> postorderTraversal(TreeNode *root) {
    if(root == nullptr) {
        return {};
    }
    
    vector<int> res;
    stack<TreeNode *> call;
    call.push(root);
    while(!call.empty()) {
        TreeNode *tmp = call.top();
        call.pop();
        if(tmp != nullptr) {
            call.push(tmp);
            call.push(nullptr);
            if(tmp->right) {
                call.push(tmp->right);
            }
            if(tmp->left) {
                call.push(tmp->left);
            }
        }
        else {
            res.push_back(call.top()->val);
            call.pop();
        }
    }
    return res;
}

分治法

　　递归（先序递归遍历，从上到下）和分治遍历（先序遍历，从下向上合并子集）区别：前者一般将结果通过参数传递，后者递归返回结果合并。

　　先分别处理局部，再合并结果。

//先序 
vector<int> inorderTraversal(TreeNode *root) {
    if(root == nullptr) {
        return {};
    }
    
    vector<int> res;
    vector<int> left = inorderTraversal(root->left);
    vector<int> right = inorderTraversal(root->right);
    
    res.push_back(root->val);
    res.insert(res.back(), left.begin(), left.end());
    res.insert(res.back(), right.begin(), right.end());
    return res;
}

BFS按层遍历

vector<vector<int>> leverOrder(TreeNode *root) {
    if(root == nullptr) {
        return {};
    }
    
    vector<vector<int>> res;
    vector<int> tmp;
    queue<TreeNode *> q;
    TreeNode *last = root, *nlast = nullptr;//last代表当前行最右结点；nlast代表下一行最右结点 
    q.push(root);
    while(!q.empty()) {
        TreeNode *cur = q.front();
        q.pop();
        tmp.push_back(cur->val);//访问操作 
        if(cur->left) {
            q.push(cur->left);
            nlast = cur->left;
        }
        if(cur->right) {
            q.push(cur->right);
            nlast = cur->right;
        }
        
        if(cur == last) { //当前节点 == 当前行最右节点证明当前行已经访问完毕 
            res.push_back(tmp);
            tmp.clear();
            last = nlast;
        }
    }
    return res;
}

DFS按层遍历

vector<vector<int>> res;
void levelOrder(TreeNode* root, int level) {
    if(root == nullptr) {
        return ;
    }
    
    if(res.size() == level) {
        res.resize(level+1);
    }
    res[level].push_back(root->val);
    levelOrder(root->left, level+1);
    levelOrder(root->right, level+1);
}

序列化与反序列化

void serialize(TreeNode* head,vector<char> &B)//先序序列化：B存放序列化结果
{
    if(!head)//1.遍历到空节点时做什么事
    {
        B.push_back('#');
        B.push_back('!');
        return;
    }
    //2.结点不为空
    int value=head->val;
    if(!value)//2.1值是否为真
    {
        B.push_back('0');
        B.push_back('!');
        serialize(head->left,B);
        serialize(head->right,B);
        return;
    }
    //数字数值可能超过一位
    int a=0;
    vector<int> A;
    while(value)
    {
        a=value%10;
        A.push_back(a);
        value/=10;
    }
    while(!A.empty())
    {
        a=A.back();
        A.pop_back();
        B.push_back('0'+a);
    }
    B.push_back('!');

    serialize(head->left,B);
    serialize(head->right,B);
    return;
}

void deserialize(vector<char> A,TreeNode* & head)//先序反序列化:#空结点，！当前结点结束,n表示当前读的字符位置,A为输入原序列
{
    int i,j,value=0;
    if((n>A.size()-1)||A[n]=='#')
        return;

    i=j=n;
    while(A[j]!='!')
        j++;
    while(j>i)
    {
        value=(A[i]-'0')+value*10;
        i++;
    }

    head=(TreeNode*)malloc(sizeof(TreeNode));
    (*head).val=value;
    (*head).right=(*head).left=NULL;
    n=i+1;
    deserialize(A,(*head).left);
    deserialize(A,(*head).right);
}

分治应用

　　适用场景

快速排序
归并排序
二叉树相关问题

　　分治法模板

递归返回条件
分段处理
合并结果

　　递归结束需要对返回结果进行合并

void _merge(vector<int>& num, int start, int mid, int end) {
    int *tmp = new int[start-end+1];//合并两个临时区
    int i = start;
    int j = mid+1;
    int k = 0;
    
    while(i <= mid && j <= end) {
        tmp[k++] = num[i] < num[j] ? num[i++] : num[j++];
    } 
    
    while(i <= mid) {
        tmp[k++] = num[i++];
    }
    while(j <= end) {
        tmp[k++] = num[j++];
    }
    
    for(i = 0; i < k; ++i) {
        num[start+i] = tmp[i];
    }
    delete []tmp;
}
void mergeSortUpToDown(vector<int>& num, int start, int end) {
    if(num.empty() || start >= end) {
        return ;
    }
    
    int mid = start+(end-start)/2;
    mergeSortUpToDown(num, start, mid);
    mergeSortUpToDown(num, mid+1, end);
    
    _merge(num, start, mid, end);
}

快排

　　快排由于是原地交换所以没有合并过程传入的索引是存在的索引（如：0、length-1 等），越界可能导致崩溃

void quickSort(vector<int>& num, int start, int end) {
    if(start >= end || num.empty()) {
        return;
    }
    
    int left = start;
    int right = end;
    int key = num[start];
    while(left < right) {
        while(left < right && num[right] >= key) {
            --right;
        }
        num[left] = num[right];
        
        while(left < right && num[left] <= key) {
            ++left;
        }
        num[right] = num[left];
    }
    
    num[left] = key;
    quickSort(num, start, left);
    quickSort(num, left+1, end);
}

题目

求给定二叉树的最大深度

　　按层求高度

int maxDepth(TreeNode* root) {
    if(!root)
        return 0;
    
    queue<TreeNode*> q;
    q.push(root);
    int depth=0;
    while(!q.empty())
    {
        ++depth;
        int layer=q.size();
        while(layer>0)//按层处理，把每层的结点处理完
        {
            auto tmp=q.front();
            q.pop();
            if(tmp->left)
                q.push(tmp->left);
            if(tmp->right)
                q.push(tmp->right);
            --layer;
        }
    }
    return depth;
}

　　分治求，先递归求左子树高度，再递归求右子树高度，合并左右子树高度返回

int maxDepth(TreeNode* root) {
    if(root == NULL)
        return 0;
    
    int leftHeight = maxDepth(root->left);
    int rightHeight = maxDepth(root->right);

    return max(leftHeight, rightHeight)+1;
}