LeetCode.二叉树总结
2019-06-09 本文已影响0人
HITZGD
二叉树结构体定义
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
二叉树通用做题的思路
1、递归法（深度优先遍历）
思路：明确在算法在每个结点需要进行的操作，然后将问题交给框架进行处理。
void traverse(TreeNode root) {
// 判断root是否为空，是一个重要的递归终止的条件。
// 算法部分
traverse(root.left);
traverse(root.right);
}
2、非递归法（广度优先遍历）
非递归方法通常需要根据要求构建一个栈或者队列，然后通过将每层的节点推入栈或队列中，进行算法操作。大体框架如下：
stack<TreeNode*> s;
s.push(root);
while(!s.empty())
{
TreeNode* node = s.top();
s.pop();
if (node->left != NULL)
{
s.push(node->left);
}
if (node->right != NULL)
{
s.push(node->right);
}
}
二叉树的初始化
这里放一个Leetcode中string格式转二叉树的初始化过程，利用思想就是广度优先搜索，代码如下：
/*字符串转TreeNode*/
/*可以通过和上面非递归算法对比发现，使用这种框架的方式还是非常好用的*/
TreeNode* stringToTreeNode(string input) {
if (!input.size()) {
return nullptr;
}
string item;
stringstream ss;
ss.str(input);
getline(ss, item, ',');
TreeNode* root = new TreeNode(stoi(item));
queue<TreeNode*> nodeQueue;
nodeQueue.push(root);
while (true) {
TreeNode* node = nodeQueue.front();
nodeQueue.pop();
if (!getline(ss, item, ',')) {
break;
}
if (item != "null") {
int leftNumber = stoi(item);
node->left = new TreeNode(leftNumber);
nodeQueue.push(node->left);
}
if (!getline(ss, item, ',')) {
break;
}
if (item != "null") {
int rightNumber = stoi(item);
node->right = new TreeNode(rightNumber);
nodeQueue.push(node->right);
}
}
return root;
}
二叉树的中序遍历
前序遍历的流程是： 根结点->左结点->右节点
中序遍历的流程是： 左结点->根结点->右节点
后序遍历的流程是： 左结点->右节点->根结点
/*树的前序遍历*/
void preOrder(TreeNode *root, vector<int> &result)
{
if (root)
{
result.push_back(root->val);
preOrder(root->left, result);
preOrder(root->right, result);
}
}
/*树的中序遍历*/
void inOrder(TreeNode *root, vector<int> &result)
{
if (root)
{
inOrder(root->left, result);
result.push_back(root->val);
inOrder(root->right, result);
}
}
/*树的后序遍历*/
void postOrder(TreeNode *root, vector<int> &result)
{
if (root)
{
postOrder(root->left, result);
postOrder(root->right, result);
result.push_back(root->val);
}
}
使用非递归法的遍历方式
/*树的中序遍历*/
vector<int> inorderTraversal(TreeNode* root)
{
vector<int> res;
stack<TreeNode*> s;
TreeNode* p = root;
while (p || !s.empty())
{
while (p)
{
s.push(p);
p = p->left;
}
p = s.top();
s.pop();
res.push_back(p->val);
p = p->right;
}
return res;
}
二叉树的常见操作
Leetcode关于二叉树有一些难度为简单的题目，这些题目通过是可以利用简单的递归来实现。
Leetcode 100.相同的树
给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例1：
输入: 1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]
输出: true
示例2：
输入: 1 1
/ \
2 2
[1,2], [1,null,2]
输出: false
解题方法：
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (p == NULL && q == NULL)
{
return true;
}
if (p == NULL || q == NULL)
{
return false;
}
if (p->val != q->val)
{
return false;
}
return isSameTree(p->right, q->right) &&
isSameTree(p->left, q->left);
}
};
Leetcode 101.对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
解题思路：
class Solution {
public:
bool isSymmetric(TreeNode* root) {
return isTree(root, root);
}
bool isTree(TreeNode* t1, TreeNode* t2)
{
if (t1 == NULL && t2 == NULL)
{
return true;
}
if (t1 == NULL || t2 == NULL)
{
return false;
}
return (t1->val == t2->val) && isTree(t1->left, t2->right) && isTree(t1->right, t2->left);
}
};
Leetcode 104. 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
解题思路：
/*递归法*/
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == NULL)
{
return 0;
}
else
{
int left_height = maxDepth(root->left);
int right_height = maxDepth(root->right);
return max(left_height, right_height) + 1;
}
}
};
/*非递归法*/
class Solution {
public:
int maxDepth(TreeNode* root) {
vector<vector<int>>dp;
queue<TreeNode*> s;
if (root == NULL)
{
return dp.size();
}
s.push(root);
while (!s.empty())
{
vector<int> temp;
int ssize = s.size();
for (int i = 0; i <ssize; i++)
{
TreeNode* node = s.front();
s.pop();
temp.push_back(node->val);
if (node->left != NULL)
{
s.push(node->left);
}
if (node->right != NULL)
{
s.push(node->right);
}
}
dp.push_back(temp);
}
return dp.size();
}
};
Leetcode 104. 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回它的最小深度 2.
解题思路：
class Solution {
public:
int minDepth(TreeNode* root) {
if (root == NULL)
{
return 0;
}
int left = minDepth(root->left);
int right = minDepth(root->right);
return (left && right) ? min(left, right) + 1 : 1 + left + right;
}
};
Leetcode 110. 平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true 。
****示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
返回 false 。
解题思路：
class Solution {
public:
bool isBalanced(TreeNode* root) {
if (!root)
{
return true;
}
if (abs(getDepth(root->left) - getDepth(root->right)) > 1)
{
return false;
}
return isBalanced(root->left) && isBalanced(root->right);
}
int getDepth(TreeNode* root)
{
if (!root)
{
return 0;
}
return 1 + max(getDepth(root->left), getDepth(root->right));
}
};
