二叉树遍历中构造前后指针

1. 何为前后指针

在二叉树的一些题目中，需要我们记录前后两个相邻节点各自的信息（尤其是在二叉搜索树中经常出现，比如501和530，那么常用的技巧就是在遍历过程中设置两个指针，分别指向这两个相邻节点，在处理之后，将前一个指针指向当前节点，当前指针指向下一个节点。

2. 递归中构造前后指针

class Solution{
    private:
        TreeNode* pre;
        void traversal(TreeNode* cur){
            if(cur == NULL)return;
            traversal(cur->left); //左
            if(pre != NULL){ //中
                //处理cur和pre
            }
            pre = cur; //将前一个指针指向当前节点
            traversal(cur->right); //右
        }
    public:
        TreeNode* getMinimumDifference(TreeNode* root){
            traversal(root);
            return root;
        }
}

这里使用的是前序遍历，实际中根据需要自行修改即可。

3. 迭代中构造前后指针

class Solution{
    public:
        TreeNode* getMinimumDifference(TreeNode* root){
            stack<TreeNode*> stk;
            if(root == NULL)return root;
            TreeNode* pre = NULL;
            TreeNode* cur = root;
            while(!stk.empty() || cur != NULL){
                if(cur != NULL){
                    stk.push(cur);
                    cur = cur->left; //左
                }else{
                    cur = stk.top();
                    stk.pop();
                    if(pre == NULL){
                        //此时cur指向初始节点（最左下或者最右下）
                    }
                    if(pre != NULL){
                        //处理pre和cur
                    }
                    pre = cur; //前一个指针指向当前节点
                    cur = cur->right; //这里和上面对应，上面始终遍历左侧，则这里等于右子节点
                }
            }
            return root;
        }
}

相比较递归中的前后指针构造，我个人更熟悉迭代法中构造前后指针。在二叉搜索树中这样的处理方式很常见，需要慢慢体会这样的写法。