1. 翻转二叉树

翻转一棵二叉树。

示例：

输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

备注:
这个问题是受到 Max Howell 的原问题启发的：

谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。

出处：

https://edu.csdn.net/practice/27729560

代码：

#include <bits/stdc++.h>
using namespace std;
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution
{
public:
    TreeNode *invertTree(TreeNode *root)
    {
        if (!root)
        {
            return root;
        }
        TreeNode *temp = root->left;
        root->left = invertTree(root->right);
        root->right = invertTree(temp);
        return root;
    }
};

输出：

2. 二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：2

示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

提示：

树中节点数的范围在 [0, 105] 内
-1000 <= Node.val <= 1000

代码：

#include <bits/stdc++.h>
#define null INT_MIN
using namespace std;

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

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

TreeNode* buildTree(vector<int>& nums)
{
    TreeNode *root = new TreeNode(nums[0]);
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    while(!q.empty() && i < nums.size())
    {
        TreeNode *cur = q.front();
        q.pop();
        if(nums[i] != null)
        {
            cur->left = new TreeNode(nums[i]);
            q.push(cur->left);
        }
        i++;
        if(i < nums.size() && nums[i] != null)
        {
            cur->right = new TreeNode(nums[i]);
            q.push(cur->right);
        }
        i++;
    }
    return root;
}

int main()
{
	Solution s;
	vector<int> root = {3,9,20,null,null,15,7};
	TreeNode* tree = buildTree(root);
	cout << s.minDepth(tree) << endl;
	
	root = {2,null,3,null,4,null,5,null,6};
	tree = buildTree(root);
	cout << s.minDepth(tree) << endl;

	return 0;
}

输出：

2
5

3. 填充每个节点的下一个右侧节点指针

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

进阶：

你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

示例：

输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。

提示：

树中节点的数量少于 4096
-1000 <= node.val <= 1000

出处：

https://edu.csdn.net/practice/27729558

代码：

#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
    int val;
    Node *left;
    Node *right;
    Node *next;
    Node() : val(0), left(NULL), right(NULL), next(NULL) {}
    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
    Node(int _val, Node *_left, Node *_right, Node *_next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
class Solution
{
public:
    Node *connect(Node *root)
    {
        if (!root)
            return nullptr;
        root->next = nullptr;
        connect_helper(root);
        return root;
    }
private:
    void connect_helper(Node *pNode)
    {
        if (!pNode)
            return;
        if (pNode->left == nullptr)
            return;
        pNode->left->next = pNode->right;
        if (pNode->right == nullptr)
            return;
        if (pNode->next != nullptr)
            pNode->right->next = pNode->next->left;
        else
            pNode->right->next = nullptr;
        connect_helper(pNode->left);
        connect_helper(pNode->right);
    }
};

输出：

附：二叉树的序列化与反序列化

class Codec
{
public:
    string serialize(TreeNode *root)
    {
        string result = "[";
        queue<TreeNode *> myQue;
        myQue.push(root);
        while (!myQue.empty())
        {
            root = myQue.front();
            myQue.pop();
            if (root == NULL)
            {
                result += "null,";
                continue;
            }
            else
            {
                result += to_string(root->val) + ",";
                myQue.push(root->left);
                myQue.push(root->right);
            }
        }
        if (result == "[null,")
        {
            result.resize(result.size() - 1);
        }
        else
        {
            int endIndex = result.size() - 1;
            while (result[endIndex] < '0' || result[endIndex] > '9')
            {
                endIndex -= 1;
            }
            result.resize(endIndex + 1);
        }
        result += "]";
        return result;
    }
    TreeNode *deserialize(string data)
    {
        vector<string> dataVec;
        int dataSize = data.size();
        for (int index = 1; index < dataSize - 1; ++index)
        {
            string tempData = "";
            while (index < dataSize - 1 && data[index] != ',')
            {
                tempData += data[index++];
            }
            dataVec.push_back(tempData);
        }
        int dataVecSize = dataVec.size();
        queue<TreeNode *> myQue;
        if (dataVec[0] == "null")
        {
            return NULL;
        }
        TreeNode *result = new TreeNode(atoi(dataVec[0].c_str())), *tempPtr;
        myQue.push(result);
        for (int index = 1; index < dataVecSize; ++index)
        {
            tempPtr = myQue.front();
            myQue.pop();
            if (dataVec[index] != "null")
            {
                tempPtr->left = new TreeNode(atoi(dataVec[index].c_str()));
                myQue.push(tempPtr->left);
            }
            index += 1;
            if (index < dataVecSize && dataVec[index] != "null")
            {
                tempPtr->right = new TreeNode(atoi(dataVec[index].c_str()));
                myQue.push(tempPtr->right);
            }
        }
        return result;
    }
};