二叉树相关面试题

1.求最短路径

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) 
    {
        int Depth = 0;
        int Tmp = 1;
        MinDepth(root,Depth,Tmp);
        return Depth;
    }
    int MinDepth(TreeNode* root,int& Depth,int Tmp)
    {
        if(root)
        {
            if(root->left == NULL && root->right == NULL)
            Depth = (Depth==0)?Tmp:(Tmp<Depth?Tmp:Depth);
            MinDepth(root->left,Depth,Tmp+1);
            MinDepth(root->right,Depth,Tmp+1);
            return Depth;
        }
        return 0;
    }
};


/*解法二*/

class Solution 
{
public:
　　int minDepth(TreeNode* root) 
　　{
        if(!root)
            return 0;
        else if (!root->left && root->right)
            return 1 + minDepth(root->right);
        else if (!root->right && root->left)
            return 1 + minDepth(root->left);
        else return 1 + min(minDepth(root->left), minDepth(root->right));
    }
};

2.按照层次打印二叉树

递归的方式：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

    
class Solution 
{
public:
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        vector<vector<int>> Vector;
        int Level = 0;
        LevelOrderBottom(root,Vector,Level);
        return Vector;
    }
    void LevelOrderBottom(TreeNode* root,vector<vector<int>>& Vector,int Level)
    {
        if(root)
        {
            ++Level;
            if(Level > Vector.size())
            Vector.resize(Level);
            Vector[Level-1].push_back(root->val);
            LevelOrderBottom(root->left,Vector,Level);
            LevelOrderBottom(root->right,Vector,Level);
        }
    }
};

非递归的方式：（利用两个队列）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        vector<vector<int>> Vector;
        queue<TreeNode*> CurLevel;
        int Level = 1;
        if(root)
        CurLevel.push(root);
        while(!CurLevel.empty())
        {
            queue<TreeNode*> NextLevel;
            while(!CurLevel.empty())
            {
                if(Level > Vector.size())
                Vector.resize(Level);
                TreeNode* root = CurLevel.front();
                CurLevel.pop();
                Vector[Level-1].push_back(root->val);
                if(root->left)
                NextLevel.push(root->left);
                if(root->right)
                NextLevel.push(root->right);
            }
            ++Level;
            CurLevel = NextLevel;
        }
        return Vector;
    }
   
};

3.之字型遍历二叉树

递归方式：（先层次遍历，然后让奇数层的逆序）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution 
{
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) 
    {
        vector<vector<int>> Vector;
        int Level = 1;
        ZigzagLevelOrder(Vector,root,Level);
        for(int i=0;i<Vector.size();++i)
        {
            if(i&1)
            {
                vector<int>::iterator it_begin = Vector[i].begin(),it_end = Vector[i].end();
                reverse(it_begin,it_end);
            }
        }
        return Vector;
    }
    void ZigzagLevelOrder(vector<vector<int>>& Vector,TreeNode* root,int Level)
    {
        if(root)
        {
            if(Level > Vector.size())
            Vector.resize(Level);
            Vector[Level-1].push_back(root->val);
            ZigzagLevelOrder(Vector,root->left,Level+1);
            ZigzagLevelOrder(Vector,root->right,Level+1);
        }
    }
};

非递归方式：（双栈）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution 
{
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) 
    {
        vector<vector<int>> Vector;
        bool Order = true;
        int Level = 1;
        stack<TreeNode*> CurLevel;
        if(root)
        CurLevel.push(root);
        while(!CurLevel.empty())
        {
            stack<TreeNode*> NextLevel;
            while(!CurLevel.empty())
            {
                TreeNode* root = CurLevel.top();
                CurLevel.pop();
                if(Level > Vector.size())
                Vector.resize(Level);
                Vector[Level-1].push_back(root->val);
                if(Order)
                {
                    if(root->left)
                    NextLevel.push(root->left);
                    if(root->right)
                    NextLevel.push(root->right);
                }
                else
                {
                    if(root->right)
                    NextLevel.push(root->right);
                     if(root->left)
                    NextLevel.push(root->left);
                }
            }
            Level++;
            Order = !Order;
            CurLevel = NextLevel;
        }
        return Vector;
    }
};

4.二叉树转换为单链表

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution 
{
public:
    void flatten(TreeNode* root)
    {
        if(root)
        {
            flatten(root->right);
            flatten(root->left);
            if(root->left)
            {
                TreeNode* tmp = root->left;
                while(tmp->right)
                tmp = tmp->right;
                tmp->right = root->right;
                root->right = root->left;
                root->left = NULL;
            }
        }
    }
};

5.二叉树的右视图

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) 
    {
        vector<int> Vector;
        int MaxLevel = 0,CurLevel = 1;
        RightSideView(root,Vector,MaxLevel,CurLevel);
        return Vector;
    }
    
    void RightSideView(TreeNode* root,vector<int>& Vector,int& MaxLevel,int CurLevel)
    {
        if(root)
        {
            if(CurLevel > MaxLevel)
            {
                MaxLevel = CurLevel;
                Vector.push_back(root->val);
            }
            RightSideView(root->right,Vector,MaxLevel,CurLevel+1);
            RightSideView(root->left,Vector,MaxLevel,CurLevel+1);
        }
    }
};

6.判断能否构成二叉树

void Check(string& preorder, int& index, bool& Post)
{
    if (preorder[index] != '')
    {
        bool left = false, right = false;
        if (preorder[index++] == '#')
        {
            Post = true;
            return;
        }

        Check(preorder, index, left);
        Check(preorder, index, right);
        Post = left && right;
    }
}

bool isValidSerialization(string preorder)
{
    bool Post = false;
    int index = 0;
    Check(preorder, index, Post);
    if (index == preorder.size());
    return Post;
    return false;
}

解法二：