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; } };
