题目来源“数据结构与算法面试题80道”。这是第三部分，包含其中的第11题到第15题。
在此给出我的解法，如你有更好的解法，欢迎留言。

问题分析：涉及的知识点是二叉树的遍历，遍历的方法主要有：

先序遍历
中序遍历
后序遍历
层次遍历
在本题中，使用先序遍历的方法。

方法：

void m_length(BSTreeNode *root, int *length, int *max_length){
    if (NULL == root ||
        (NULL == root->m_pLeft && NULL == root->m_pRight)){
        if ((*length) > (*max_length)) (*max_length) = (*length);
        return;
    }
    (*length) ++;
    m_length(root->m_pLeft, length, max_length);
    (*length) --;

    (*length) ++;
    m_length(root->m_pRight, length, max_length);
    (*length) --;
}

问题分析：可以使用类的构造方法，在类的每次实例化对象时都会调用构造方法，那么只需要实例化n个对象，就会调用n次构造方法，这就模拟了循环的过程，此时，只需要有一个全局变量记录累加的值即可。

方法：

#include <stdio.h>

class calnum{
    public:
        calnum(){
            n ++;
            sum += n;
        }
        ~calnum(){}

        int get_num(){
            return sum;
        }
    private:
        static int sum;
        static int n;
};

int calnum::sum = 0;
int calnum::n = 0;

int main(){
    // 声明n个对象
    calnum *sum = new calnum[100];

    printf("%d\n", sum->get_num());

    delete[] sum;
    return 1;
}

问题分析：遍历一遍链表的时间复杂度为O(n)，但是链表节点的遍历只能按顺序遍历，问题中是需要取到倒数第k个，最直接的想法是遍历两遍链表，第1遍得到链表的长度，第2遍是取到倒数第k个；那么能否只遍历一遍就能取到倒数第k个节点，最关键的点是需要确定链表的长度，我们可以使用双指针的方法：第一个指针用于遍历整个链表，第二个链表用于遍历部分链表，第一个指针比第二个指针多走k步，当第一个指针遍历完链表，第二个指针所指的即为倒数第k个数，如下图所示：

方法：

ListNode* get_reverse_k(ListNode *head, int k){
    if (NULL == head) return NULL;

    ListNode *p = head;
    ListNode *q = head;
    int step = 0;
    while (NULL != p->m_pNext){
        if (step >= k){
            q = q->m_pNext;
        }
        p = p->m_pNext;
        step ++;
    }
    if (step < k) return NULL;
    else return q;
}

问题分析：时间复杂度为O(n)，即只能遍历一次数组，考虑到数组是排好序的，考虑从头部和从尾部同时向数组的中部遍历，假设i从头部遍历，j从尾部开始遍历：

• 如果a[i] + a[j] == num，直接返回；
• 如果a[i] + a[j] > num，应该减小其和的值，则减小j;
• 如果a[i] + a[j] < num，应该增大其和的值，则增加i;

方法：

void get_sum(int *a, int length, int n){
    if (NULL == 0 || length <= 0) return;

    int start = 0;
    int end = length - 1;
    while (start < end){
        if (a[start] + a[end] == n){
            printf("%d,%d\n", a[start], a[end]);
            break;
        }else if (a[start] + a[end] > n){
            end --;
        }else{
            start ++;
        }
    }
}

问题分析：实质上仍然是二叉树的遍历，上述已经介绍过二叉树的不同的遍历方法，当遍历到每一个节点的时候，交换其左右子树，依次下去，直到叶子节点。

方法：

1、递归的方法：

void tree_swap(BSTreeNode *root){
    BSTreeNode *p_tmp = root->m_pLeft;
    root->m_pLeft = root->m_pRight;
    root->m_pRight = p_tmp;
}

void tree_mirror(BSTreeNode *root){
    if (NULL == root ||
        (NULL == root->m_pLeft && NULL == root->m_pRight)){
        return;
    }

    tree_swap(root);
    tree_swap(root->m_pLeft);
    tree_swap(root->m_pRight);
}

2、循环的方法

void tree_mirror_loop(BSTreeNode *root){
    if (NULL == root ||
        (NULL == root->m_pLeft && NULL == root->m_pRight)){
        return;
    }

    BSTreeNode *p = root;
    queue<BSTreeNode *> q_tree;
    q_tree.push(p);
    while (! q_tree.empty()){
        BSTreeNode *q = q_tree.front();
        q_tree.pop();
        if (NULL != q->m_pLeft || NULL != q->m_pRight){
            tree_swap(q);
        }
        if (NULL != q->m_pLeft) q_tree.push(q->m_pLeft);
        if (NULL != q->m_pRight) q_tree.push(q->m_pRight);
    }
}