前言

面试中的树都是二叉树，即有左右两个节点的树
牢记：root->left表示左子树，root->right表示右子树，通过树的递归解决问题

求树的高

int BT_depth(TreeNode* root){
    if(root==NULL)
        return 0;
    int depth;
    depth=1+max(BT_depth(root->left),BT_depth(root->right));
    return depth;
}

前序遍历

即：先根遍历

void preorderTraversal(TreeNode* root){
    if(root==NULL)
        return;
    cout<<root->val<<" ";
    preorderTraversal(root->left);
    preorderTraversal(root->right)；
}

中序遍历

即：中根遍历

void inorderTraversal(TreeNode* root){
    if(root==NULL)
        return;
    inorderTraversal(root->left);
    cout<<root->val<<" ";
    inorderTraversal(root->right)；
}

后序遍历

即：后根遍历

void postorderTraversal(TreeNode* root){
    if(root==NULL)
        return;
    postorderTraversal(root->left);
    postorderTraversal(root->right)；
    cout<<root->val<<" ";
}

非递归前序遍历

递归->非递归利用栈

创建栈
将根节点压入栈
While 栈非空
    弹出一个节点
    打印它的值
    If 存在右节点，将右节点压入栈
    IF 存在左节点，将左节点压入栈

void preorderTraversal2(TreeNode* root){
    if(root==NULL)
        return;
    stack<TreeNode*> stk;
    stk.push(root);
    while(!stk.empty()){
        TreeNode *pNode =stk.top();
        stk.pop();
        cout<<pNode->val<<endl;
        if(pNode->right!=NULL)
            stk.push(pNode->right);
        if(pNode->left!=NULL)
            stk.push(pNode->left);

    }

}

算法O(n)

非递归中序遍历

初始化一个二叉树结点pNode指向根结点；
若pNode非空，那么就把pNode入栈，并把pNode变为其左孩子；（直到最左边的结点）
若pNode为空，弹出栈顶的结点，并访问该结点，将pNode指向其右孩子（访问最左边的结点，并遍历其右子树）

void inOrderTraversal2(TreeNode *root) {
    if(root == NULL)
        return;
    stack<TreeNode *> stk;
    TreeNode *pNode = root;
    while(pNode != NULL || !stk.empty()) {
        if(pNode != NULL) {
            stk.push(pNode);
            pNode = pNode->left;
        }
        else {
            pNode = stk.top();
            stk.pop();
            cout << pNode->val << endl;
            pNode = pNode->right;
        }
    }
}

非递归后序遍历

设置两个栈stk, stk2；
将根结点压入第一个栈stk；
弹出stk栈顶的结点，并把该结点压入第二个栈stk2；
将当前结点的左孩子和右孩子先后分别入栈stk；
当所有元素都压入stk2后，依次弹出stk2的栈顶结点，并访问之。

第一个栈的入栈顺序是：根结点，左孩子和右孩子；于是，压入第二个栈的顺序是：根结点，右孩子和左孩子。因此，弹出的顺序就是：左孩子，右孩子和根结点。

void postOrder2(TreeNode *root) {
    if(root == NULL)
        return;

    stack<TreeNode *> stk, stk2;
    stk.push(root);
    while(!stk.empty()) {
        TreeNode *pNode = stk.top();
        stk.pop();
        stk2.push(pNode);
        if(pNode->left != NULL)
            stk.push(pNode->left);
        if(pNode->right != NULL)
            stk.push(pNode->right);
    }
    while(!stk2.empty()) {
        cout << stk2.top()->val << endl;
        stk2.pop();
    }
}

复杂度分析

二叉树遍历的非递归实现，每个结点只需遍历一次，故时间复杂度为O(n)。而使用了栈，空间复杂度为二叉树的高度，故空间复杂度为O(n)。

二叉树转堆

问题：给定一个存储于一个无序的二叉树中的整数集合。使用数组排序算法将这个树转化为一个堆，这个堆使用一个平衡二叉树作为底层的数据结构。

其他参考

二叉树

前言