二叉树问题（一）-LeetCode 110、617、101、814、655、98、654（递归思路）
- 2019 年 12 月 24 日
- 笔记
作者：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
