Leetcode -110.平衡二叉树
题目：给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例 1：
输入：root = [3, 9, 20, null, null, 15, 7]
输出：true
示例 2：
输入：root = [1, 2, 2, 3, 3, null, null, 4, 4]
输出：false
示例 3：
输入：root = []
输出：true
提示：
树中的节点数在范围[0, 5000] 内
- 10^4 <= Node.val <= 10^4
思路：化为子问题计算每颗子树的左右子树高度；结束条件为子树的左右子树高度差大于1；
//计算子树的高度 int TreeHeight(struct TreeNode* root) { if (root == NULL) return 0; int h1 = TreeHeight(root->left) + 1; int h2 = TreeHeight(root->right) + 1; //返回深度较高的 return h1 > h2 ? h1 : h2; } bool isBalanced(struct TreeNode* root) { if (root == NULL) return true; //判断当前根的左右子树高度差是否大于1 if (abs(TreeHeight(root->left) - TreeHeight(root->right)) > 1) return false; //如果当前根左右子树高度差小于等于1，递归其左子树的根和右子树的根进行判断 return isBalanced(root->left) && isBalanced(root->right); }
Leetcode -226.翻转二叉树
题目：给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4, 2, 7, 1, 3, 6, 9]
输出：[4, 7, 2, 9, 6, 3, 1]
示例 2：
输入：root = [2, 1, 3]
输出：[2, 3, 1]
示例 3：
输入：root = []
输出：[]
提示：
树中节点数目范围在[0, 100] 内
- 100 <= Node.val <= 100
思路：化为子问题左根的左指针指向右根的右指针，右根的右指针指向左根的左指针；左根的右指针指向右根的左指针，右根的左指针指向左根的右指针；结束条件为空；
struct TreeNode* invertTree(struct TreeNode* root) { if (root == NULL) return NULL; //将当前左根和右根记录下来 struct TreeNode* LeftRoot = invertTree(root->left); struct TreeNode* RightRoot = invertTree(root->right); //根的左右子树交换 root->left = RightRoot; root->right = LeftRoot; return root; }
