二叉树问题（一）-LeetCode 110、617、101、814、655、98、654（递归思路）
二叉树问题（一）-LeetCode 110、617、101、814、655、98、654（递归思路）
作者：TeddyZhang，公众号：算法工程师之路
二叉树问题（一）：
LeetCode # 110 617 101 814 655 98 654
1
编程题
【LeetCode #110】平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。 本题中，一棵高度平衡二叉树定义为： 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过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 height(TreeNode* node) {
if (node == nullptr) return ;
return max(height(node->left), height(node->right)) + ;
}
bool isBalanced(TreeNode* root) {
if (root == nullptr) return true;
int left = height(root->left);
int right = height(root->right);
return abs(left-right) <= && isBalanced(root->left) && isBalanced(root->right);
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/balanced-binary-tree/
【LeetCode #617】合并二叉树
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
/**
* 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:
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if (t1 == nullptr) return t2;
if (t2 == nullptr) return t1;
if (t1 && t2) {
t1->val += t2->val;
t1->left = mergeTrees(t1->left, t2->left);
t1->right = mergeTrees(t1->right, t2->right);
return t1;
}else return nullptr;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/merge-two-binary-trees
【LeetCode #101】对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1 / \ 2 2 / \ / \ 3 4 4 3
class Solution {
public:
bool dfs(TreeNode* left, TreeNode* right) {
if (left == nullptr && right == nullptr)
return true;
if (!left || !right)
return false;
if (left->val != right->val){
return false;
} else {
return dfs(left->left, right->right) && dfs(left->right, right->left);
}
}
bool isSymmetric(TreeNode* root) {
return dfs(root, root);
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/symmetric-tree
【LeetCode #814】二叉树剪枝
给定二叉树根结点 root ，此外树的每个结点的值要么是 0，要么是 1。
返回移除了所有不包含 1 的子树的原二叉树。
( 节点 X 的子树为 X 本身，以及所有 X 的后代。)
示例1: 输入: [1,null,0,0,1] 输出: [1,null,0,null,1]
解题思路：
遍历的查找每个节点，然后判断该二叉树的某个子树中是否存在节点值为1的数字，如果存在，则对应子树的根节点置为nullptr，否则就不变化。
class Solution {
public:
bool containOne(TreeNode* root) {
if (root == nullptr) return false;
bool ll = containOne(root->left);
bool rr = containOne(root->right);
if (!ll) {
root->left = nullptr;
}
if (!rr) {
root->right = nullptr;
}
return ll || rr || root->val == ;
}
TreeNode* pruneTree(TreeNode* root) {
containOne(root);
return root;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binary-tree-pruning
【LeetCode #655】输出二叉树
在一个 m*n 的二维字符串数组中输出二叉树，并遵守以下规则：
行数 m 应当等于给定二叉树的高度。 列数 n 应当总是奇数。 根节点的值（以字符串格式给出）应当放在可放置的第一行正中间。根节点所在的行与列会将剩余空间划分为两部分（左下部分和右下部分）。你应该将左子树输出在左下部分，右子树输出在右下部分。左下和右下部分应当有相同的大小。即使一个子树为空而另一个非空，你不需要为空的子树输出任何东西，但仍需要为另一个子树留出足够的空间。然而，如果两个子树都为空则不需要为它们留出任何空间。 每个未使用的空间应包含一个空的字符串""。 使用相同的规则输出子树。
示例 1: 输入: 1 / 2 输出: [["", "1", ""], ["2", "", ""]]
解题思路：
首先求出二叉树的高度m，进而得到n = pow(1, m)-1; 然后我们二分的进行输出到二维vector中，使用二分法。
/**
* 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<string>> printTree(TreeNode* root) {
int m = getHeight(root);
int n = pow(, m) - ;
vector<vector<string>> res(m, vector<string>(n, ""));
dfsPrint(root, res, , , n-1);
return res;
}
private:
int getHeight(TreeNode* node) {
if (node == nullptr) return ;
return max(getHeight(node->left), getHeight(node->right)) + ;
}
void dfsPrint(TreeNode* root, vector<vector<string>>& res, int row, int start, int end) {
if(!root || (start > end)) return;
int mid = start + (end - start) / ;
res[row][mid] = to_string(root->val);
dfsPrint(root->left, res, row+, start, mid);
dfsPrint(root->right, res, row+, mid+, end);
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/print-binary-tree
【LeetCode #98】验证二叉搜索树
给定一个二叉树，判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1: 输入: 2 / \ 1 3 输出: true
解题思路：
复习中序遍历，对二叉树进行中序遍历，并使用pre节点储存当前节点的上一节点，然后保证边界结果为递增序列即可！
/**
* 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:
bool isValidBST(TreeNode* root) {
stack<TreeNode*> sta;
TreeNode* pre = nullptr;
TreeNode* cur = root;
while(cur != nullptr || !sta.empty()) {
if (cur != nullptr) {
sta.push(cur);
cur = cur->left;
}else {
cur = sta.top();
sta.pop();
if (pre && (pre->val >= cur->val)) {
return false;
}
pre = cur;
cur = cur->right;
}
}
return true;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/validate-binary-search-tree
【LeetCode #654】最大二叉树
给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：
二叉树的根是数组中的最大元素。
- 左子树是通过数组中最大值左边部分构造出的最大二叉树。
- 右子树是通过数组中最大值右边部分构造出的最大二叉树。
- 通过给定的数组构建最大二叉树，并且输出这个树的根节点。
解题思路：
首先找到最大值，然后构建结点，从最大值位置分成两个区间，然后分别使用相应的区间构造root的左右子树，递归构造即可！
/**
* 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:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
if(nums.size() == ) return nullptr;
auto it = max_element(nums.begin(), nums.end());
TreeNode* root = new TreeNode(*it);
vector<int> ll(nums.begin(), it);
vector<int> rr(it+, nums.end());
root->left = constructMaximumBinaryTree(ll);
root->right = constructMaximumBinaryTree(rr);
return root;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/maximum-binary-tree
腾讯云开发者
