二叉树有关的高频面试题_找到搜索二叉树中两个错误的节点

案例一：折纸练习题

请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折一次，压出折痕后展开。此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折两次，压出折痕后展开，此时有三条折痕，从上到下一次是下折痕，下折痕和上折痕。给定给一个输入参数N，代表纸条都从下标向上方连续对折N次，请从上到下打印所有折痕的方向。

注意：上面的题目的要求是从上到下打印所有折痕的方向，也就是说打印的折痕的顺序是确定的，从上到下打印。

通过亲手实践我们知道，第一次对折产生的折痕是下，第二次对折在第一次对折产生的折痕的上下两边形成一个下和上折痕，以此类推，其实每一次对折都会在每个已有的折痕的上下两边产生下 上两个折痕、在这里一定要注意顺序，也就是说对于已有的折痕来说，对折之后的折痕从上到下变成 “下   已有折痕   上“。

所有折痕的结构是一个满二叉树的结构，头节点为下，每一个左子树头节点为上，每一个右子树头节点为下。具体信息如下所示：

因此从上到下打印所有折痕方向，实际上就是实现先右再中最后左的遍历，就是所有折痕的打印顺序。用递归。

class FoldPaper {
public:
    struct TreeNode{
    TreeNode* left;
    TreeNode* right;
    string val;
    TreeNode(string x):val(x),left(NULL),right(NULL){}
};


    vector<string> foldPaper(int n) {
        // write code here
        vector<string> result;
        int count=1;
        if(count==n){
            result.push_back("down");
            return result;
        }
        
        //生成二叉树
       TreeNode* root=getTree(n);
        //右孩子 根节点 左孩子 遍历二叉树
        getString(root,result);
        return result;
    
        }
    
    void getString(TreeNode* root, vector<string>& result){
        if(root==NULL)
            return;
        getString(root->right,result);
        result.push_back(root->val);
        getString(root->left,result);
    }
    
    TreeNode* getTree(int n){
        int count=1;
        TreeNode* root=new TreeNode("down");
        TreeNode* last=root;;
        TreeNode* nlast;
        queue<TreeNode*> temp;
        TreeNode* cur;
        temp.push(root);
        
        while(!temp.empty()){
            cur=temp.front();
            temp.pop();
            TreeNode* left=new TreeNode("up");
            TreeNode* right=new TreeNode("down");
            cur->left=left;
            cur->right=right;
            temp.push(left);
            temp.push(right);
            nlast=right;
            if(cur==last){
               count++;
                if(count==n)
                    break;
               last=nlast;
            }
        }
        return root;
    }
   
};

上面的程序是先建立二叉树，然后再对二叉树进行 右 中 左的遍历，比较麻烦！！但是实际上，用一个简单的递归就可以实现的。因为对于这棵二叉树来说，我们已经知道了它的左孩子一定是“上”，右孩子一定是“下”，因此，直接进行递归就可以了，不需要建立二叉树。具体的实现如下：

class FoldPaper {
public:
	void fold(int i,int N,bool down,vector &ret){
		if(i > N) return;
		fold(i + 1,N,true,ret);
		ret.push_back(down ? "down" : "up");
		fold(i + 1,N,false,ret);
	}
    vector foldPaper(int n) {
		vector ret;
		fold(1,n,true,ret);
		return ret;
    }
};

案例二：一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，使得这棵二叉树不再是搜索二叉树，请找到这两个错误的节点。

1. 对二叉树进行中序遍历，依次出现的节点值会一直升序，如果两个节点值错了，会出现降序。

2. 如果在中序遍历时节点值出现了两次降序，第一个错误的节点为第一次降序时较大的节点，第二个错误的节点为第二次降序时较小的节点。

3. 如果在中序遍历的时候节点值只出现了一次降序，第一个错误的节点为这次降序时较大的节点，第二个错误的节点为这次降序时较小的节点。

4. 因此改写一个基本的二叉树中序遍历就可以了。递归或者非递归都可以。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/


class FindErrorNode {
public:
    vector<int> findError(TreeNode* root) {
        // write code here
        vector<int> result;//这里面存放的结果，也就是调换了位置的值，小的在前
        vector<int> temp;
        Inorder(root,temp);
        int A=0;
        int B=0;
        vector<int>::iterator iter=temp.begin();
        int flag=1;
        while(iter!=temp.end()){
            if(*iter<*(iter+1)){
                iter++;
                continue;
            }
            else if(flag==1){
                    A=*iter;
                    flag=0;
                    iter++;
                    B=*iter;//这里一定更要注意，因为有可能是相邻两个数进行了交换
            }else if(flag==0){
                B=*(++iter);
                break;
            }
        }
        result.push_back(B);
        result.push_back(A);
        return result;
    }
    void Inorder(TreeNode* root, vector<int>& result){
        if(root==NULL)
            return ;
        Inorder(root->left,result);
        result.push_back(root->val);
        Inorder(root->right,result);
    }
};

对于上面的实现来说，一定更要注意相邻两个数交换的情况！！

案例三：从二叉树的节点A出发，可以向上或者向下走，但沿途的节点只能经过一次，当到达节点B时，路径上的节点数（包括起始节点和终止节点）叫做A到B的距离。

给定一棵二叉树的头节点head，求整棵树上节点间的最大距离。

一个以h为头的树上，最大距离只可能来自以下三种情况：

情况一：h的左子树上的最大距离。

情况二：h的右子树上的最大距离。

情况三：h左子树上离h左孩子最远的距离，加上h自身这个节点，再加上右子树上离h右孩子的最远距离，也就是两个节点分别来自h两侧子树的情况。

三个值中最大的那个就是以h为头的整棵树上最远的距离。

具体步骤：

1. 整个过程为后序遍历，在二叉树的每棵子树上执行步骤2。

2. 假设子树头为h，处理h左子树，得到两个信息，左子树上的最大距离记为LMax1，左子树上距离h左孩子的最远距离记为LMax2，处理h右子树得到右子树上的最大距离记为RMax1，距离h右孩子的最远距离记为RMax2，那么跨h节点情况下的最大距离为LMax2+1+RMax2,这个值与LMax1和RMax1比较，最大值为，以h为头的树上的最大距离。

3. LMax2+1就是h左子树上离h最远的点到h的距离，RMax2+1就是h右子树上离h最远的点到h的距离。选两者中最大的一个作为h树上距离h最远的距离返回。

4. 用返回长度为2的数组的方式或者加入全局变量更新的方式，可以做到返回两个值，分别为以h为头节点的节点之间的最大距离以及距离h最远的距离。

注意：对二叉树遍历的改写一定更要多加练习！！！

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/


class LongestDistance {
public:
    int findLongest(TreeNode* root) {
        // write code here
        int depthleft=findnodemax(root->left,0);
        int depthright=findnodemax(root->right,0);
        int whole=depthleft+1+depthright;
        int leftlength=findmax(root->left);
        int rightlength=findmax(root->right);
        int max=whole;
        if(max<leftlength)
            max=leftlength;
        if(max<rightlength)
            max=rightlength;
        return max;
    }
    int findmax(TreeNode* root){//需要注意的是在求以root为根的树的最大路径长度的时候，里面一定要计算三个距离，一个是root左孩子为根的树里面的最大路径长度，也就是
        //对root的左孩子调用findmax函数；一个是root右孩子为根的树里面的最大路径长度，也就是对root的右孩子调用findmax函数；还有一个是计算距离root左孩子最远的距离
        //加上1再加上距离root右孩子最远的距离；然后进行这三个值的比较，选出最大值！！！其中最后一个距离是最重要的，一定不能忘记！！！
        if(root==NULL)
            return 0;
        int leftlength=findmax(root->left)+1;
        int rightlength=findmax(root->right)+1;
        int depthleft=findnodemax(root->left,0);
        int depthright=findnodemax(root->right,0);
        int whole=depthleft+1+depthright;
        int max=leftlength;
        if(max<rightlength)
            max=rightlength;
        if(max<whole)
            max=whole;
        return max;
    }
    int findnodemax(TreeNode* root,int depth){
        //这个函数的返回值是距离root最远的节点距离,包括节点root在内的！！
        if(root==NULL)
            return depth;
        int depth1=findnodemax(root->left,depth+1);
        int depth2=findnodemax(root->right,depth+1);
        if (depth1>depth2)
            return depth1;
        else
            return depth2;
        
    }
};

上面的实现过程中，需要注意的是，在求解左边子树的最大距离的时候，和整体以root为根的树的最大距离的计算是相似的！！只不过在findmax里面，对findmax进行递归的时候要加一。但是在 findLongest函数中，调用findmax就只是调用，不需要加一！！

其实上面的算法实现不是特别精炼，也没有体现出这个算法真正的精髓！！！下面的解法非常值得参考，来自于http://m.blog.csdn.net/qq_27703417/article/details/55212833：

题目：从二叉树的节点A出发，可以向上或者向下走，但沿途的节点只能经过一次，当到达节点B时，路径上的节点数叫作A到B的距离。对于给定的一棵二叉树，求整棵树上节点间的最大距离。给定一个二叉树的头结点root，请返回最大距离。保证点数大于等于2小于等于500.

思路：理解题目的含义，对于一棵以root为根的二叉树，树上的最大距离可能来自3中情况：

情况1：完全来自root的左子树，如图所示，即最大路径不经过root结点，只在结点1的左子树2上面，此时的最大距离为8。

情况2：完全来自root结点的右子树，如图所示，最大路径不经过root结点，只在结点1的右侧左子树3上面，此时最大距离是9。

情况3：来自结点root的两侧，如图所示，经过root结点，此时的最大距离=root的左子树的高度（即结点3的最长路径）+root右子树的高度（即结点3的最长路径）+root结点本身。

分析可知，要计算结点root所在子树的最长距离，需要已知：左子树②的最长距离LMaxLength，左子树的高度LHeight；右子树③的最长距离RMaxLength，右子树的高度RHeight.然后比较Math.max(LMax,RMax,(LHeight+RHeight+1))，其最大值就是这棵二叉树的最大距离，即对于每个子树，需要求出它的最大距离和最大高度。显然这就是一个递推关系式，可以使用递归来实现，即设计一个递归函数，给定一个根结点root,求出这个根结点的最大距离max和最大高度height并返回这2个数值。其中maxLength= Math.max(LMax,RMax,(LHeight+RHeight+1))；而由于要返回这棵子树的高度，如何求子树的高度呢？二叉树的高度就是它的2个子树高度中的较大值再加上1，即height=Math.max(LHeight, RHeight)+1;

递归的递推关系有了，关键是找到递归的起始条件或者理解为终止条件。这里使用的思想是后序遍历（先遍历左右子树再处理结论），联系二叉树的后序遍历算法，进行改编。显然if(root==null)时:max=0;height=0;

总结：设计一个递归函数，输入根结点root，求出这棵二叉树的最大距离maxLength和高度length并返回。递推关系为：

maxLength= Math.max(LMax,RMax,(LHeight+RHeight+1))；

height=Math.max(LHeight, RHeight)+1

边界条件为：

if(root==null) return max=0;height=0;

在Java中不能分开返回2个值，因此要将2个值整合成为一个数组进行返回即可。

importjava.util.*;

//求二叉树上结点的最大距离：递归；最大值只可能来自3中情况

publicclass LongestDistance {

    public int findLongest(TreeNode root) {

       //特殊输入

        if(root==null) return 0;

       //调用递归函数来求得最大距离maxLength和高度height

        int[] results=this.process(root);

       //返回结果

        return results[0];

    }

   //这是一个递归方法，用于求出一个二叉树的最大距离和高度并返回这2个值

    private int[] process(TreeNode root){

         int[] tempResults=new int[2];

       //边界条件

        if(root==null){

            tempResults[0]=0;

            tempResults[1]=0;

            return tempResults;

        }

       //最大值来自3中情况，进行比较

       //左子树的结果：

        int[]paramLeft=this.process(root.left);

        int LMaxLength=paramLeft[0];

        int LHeight=paramLeft[1];

       //右子树的结果：

        int[] paramRight=this.process(root.right);

        int RMaxLength=paramRight[0];

        int RHeight=paramRight[1];

       //比较得到最大值和高度，并组成数组返回,常识：Math.max()函数只能比较2个数的大小

       //递归的递推关系

       tempResults[0]=Math.max(Math.max(LMaxLength,RMaxLength),LHeight+RHeight+1);

       tempResults[1]=Math.max(LHeight,RHeight)+1;

       //带有返回值的递归函数

        return tempResults;

    }

}

常识：Math.max()函数只能放入2个参数，即只能比较2个数的大小，如果需要比较更多数的大小，那么在Math.max()里面再套用Math.max()即可。

下面的代码是根据上面这篇博客的启发重新写的：

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/


class LongestDistance {
public:
    int findLongest(TreeNode* root) {
        // write code here
        vector<int> result=recur(root);
        return result[0];
    }
     vector<int> recur(TreeNode* root){
         vector<int> temp(2,0);
         if(root==NULL){
             temp[0]=0;//第一个里面存放的是以root为根的子树的最大距离
             temp[1]=0;//第二个里面存放的是以root为根的子树的高度，包括root
             return temp;
         }
         vector<int> lefttemp;
         lefttemp=recur(root->left);
         vector<int> righttemp;
         righttemp=recur(root->right);
         int leftheight=lefttemp[1];
         int rightheight=righttemp[1];
         int leftdis=lefttemp[0];
         int rightdis=righttemp[0];
         temp[0]=max(max(leftdis,rightdis),leftheight+rightheight+1);
         temp[1]=max(leftheight,rightheight)+1;
         return temp;       
    }
};

唯一需要记住的是对于每一个root，都要保存以它为根的子树的最大距离，以及它的高度，注意这个高度是包括它自己的！！！

案例四：给定一棵二叉树的头节点head，已知其中所有节点的值都不一样，找到含有节点最多的搜索二叉子树，并返回这棵子树的头节点。

分析：以节点node为头的树中，最大的搜索二叉子树只可能来自以下两种情况：

1. 来自node左子树上的最大搜索二叉子树是以node左孩子为头的，并且来自node右子树上的最大搜索二叉子树是以node右孩子为头的，node左子树上的最大搜索二叉子树的最大值小于node的节点值，node右子树上的最大搜索二叉子树的最小值大于node的节点值。那么以节点node为头的整棵树都是搜索二叉树。

2. 如果不满足第一种情况，说明以节点node为头的树整体不能连成搜索二叉树，这种情况下，以node为头的树上的最大搜索子树是来自node的左子树上的最大搜索 二叉树和来自node的右子树上的最大搜索二叉子树之间，节点数较多的那个。

通过以上分析，求解的具体过程如下：

1. 整体过程是二叉树的后序遍历；

2. 遍历到当前节点记为cur时 ，先遍历cur的左子树并收集4个信息，分别是左子树上，最大搜索二叉子树的头节点、节点数、树上最小值和树上最大值，在遍历cur的右子树，也要收集和上面的类似的四个信息。

3. 根据步骤2所收集的信息，判读爱是否满足第一种情况，也就是是否以cur为头的子树，整体都是搜索二叉树，如果满足第一种情况，就返回cur节点。如果满足第二个情况，就返回左子树和右子树各自的最大搜索二叉树中，节点数较多的那个树的头节点。

4. 对于如何返回4个信息，可以使用去全局变量更新的方式。当然也可以使用数组的形式。

如何判断一棵树是否为二叉排序树？

bool decide(TreeNode* root){//这是判断以root为根的子树是否为搜索二叉树的
        if(root->left==NULL&&root->right==NULL)
            return true;
        if(root->left!=NULL&&(root->left->val)<root->val){
            if(root->right!=NULL){
                if((root->right->val)>root->val)
                    return decide(root->left)&&decide(root->right);
                else
                    return false;
            }else
                return decide(root->left);
        }else if(root->left==NULL){
            if((root->right->val)>root->val)
                return decide(root->right);
            else
                return false;
        }else
            return false;
    }

上面的程序是一个错误的程序，因为它只是比较root、root的left以及root的right这三个之间的大小关系。上面的程序是无法正确判断一个二叉树是否是一个搜索二叉树的！！！！

可以采用中序遍历的方式，同时记录刚刚访问过的节点，和当前节点进行比较：

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class MaxSubtree {
public:
    TreeNode* getMax(TreeNode* root) {
        // write code here
        TreeNode* head=NULL;
        vector<int> result(3,0);
        result=postCur(root,head);
        return head;
    }
    vector<int> postCur(TreeNode* root,TreeNode*& head){//这里的head应该为引用类型的指针 ！！！！
        //因为这个函数里面有递归调用，调用的时候，比如对于left=postCur(root->left,lefthead);这里面lefthead变量，在函数里面会对lefthead进行修改，但是如果
        //不用引用的话，只是对形式参数head进行修改，并没有对lefthead进行修改，所以需要用引用类型！！
      
        vector<int> left(3,0);
        vector<int> right(3,0);
        vector<int> result(3,0);
        TreeNode* lefthead=NULL;
        TreeNode* righthead=NULL;
        if(root->left==NULL&&root->right==NULL){
            head=root;
            result[0]=(1);
            result[1]=(root->val);
            result[2]=(root->val);
            return result;
        }
        if(root->left!=NULL)
           left=postCur(root->left,lefthead);
        if(root->right!=NULL)
           right=postCur(root->right,righthead);
        if(root->left!=NULL&&root->right!=NULL&&lefthead==root->left&&righthead==root->right&&left[1]<(root->val)&&right[2]>(root->val))
        {
                  head=root;
                result[0]=(left[0]+1+right[0]);//第一个是节点的总数量
                result[1]=right[1];//第二个是最大值
                    result[2]=left[2];//第三个是最小值
                    return result; 
        }//注意！！！下面的两种情况是一定更要考虑的！！！
        else if((root->right==NULL)&&(lefthead==root->left)&&(left[1]<root->val)){//说明左子树不是空，因为前面两个都为空的情况已经考虑过了
            //这里的if里面还应该加一个判断，就是它的左子树是否为搜索二叉树，如果不是的话，就直接返回左子树里面的最大搜索二叉树！！！z这里面是借助于
            //lefthead==root->left来判断的！！！
            head=root;
            result[0]=left[0]+1;
            result[1]=root->val;
            result[2]=left[2];
            return result;
        }else if((root->left==NULL)&&(righthead==root->right)&&(right[2]>root->val)){//说明右子树不是空，左子树空
            head=root;
            result[0]=right[0]+1;
            result[1]=right[1];
            result[2]=root->val;
            return result;
        }else{
            if(left[0]>right[0]){
                head=lefthead;
                return left;
            }else if(left[0]<right[0]){
                head=righthead;
                return right;
            }else{
               
               if(lefthead->val>righthead->val){
                   head=lefthead;
                   return left;
               }else{
                   head=righthead;
                   return right;
               }
           
              }    
        }
    }
        
};

上面程序实现的过程需要注意的一共两点：

第一，postCur函数中的head参数必须是引用的类型，否则的话，left=postCur(root->left,lefthead);这里面对lefthead进行的参数传递就会失败，因为如果只是普通的函数参数的话，head和lefthead是两个不同的形式参数，对head的改变不会对lefthead产生影响！

第二，这个算法的实现需要注意的就是记录四个值以及需要注意的两种情况！！