144. 二叉树的前序遍历
难度简单
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：
输入：root = [ ]
输出：[ ]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[1,2]
示例 5：
输入：root = [1,null,2]
输出：[1,2]
提示：
- 树中节点数目在范围 [0, 100] 内
- -100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ /** * Note: The returned array must be malloced, assume caller calls free(). */ int* preorderTraversal(struct TreeNode* root, int* returnSize){ }
解析代码：
ps（迭代算法我们要学了C++之后的高阶数据结构再实现）
int TreeSize(struct TreeNode* root) { if(root==NULL) { return 0; } return 1 + TreeSize(root->left) + TreeSize(root->right); } void _preorderTraversal(struct TreeNode* root,int* array,int* pi) // (函数前面的_代表这个函数的子函数，通常用来递归) { if(root==NULL) { return; } array[(*pi)++] = root->val;//注意这里就是要传i的地址的原因（不然每个栈帧都有一个i） _preorderTraversal(root->left,array,pi); _preorderTraversal(root->right,array,pi); } int* preorderTraversal(struct TreeNode* root, int* returnSize){ int size = TreeSize(root); int* array=(int*)malloc(sizeof(int)*size); int i = 0; _preorderTraversal(root,array,&i); *returnSize=size; return array; }
（写完这题可以去写写二叉树的中序遍历和后序遍历，都是一样的）链接：
965. 单值二叉树
难度简单
如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回 true；否则返回 false。
示例 1：
输入：[1,1,1,1,1,null,1]
输出：true
示例 2：
输入：[2,2,2,5,2]
输出：false
提示：
- 给定树的节点数范围是 [1, 100]。
- 每个节点的值都是整数，范围为 [0, 99] 。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ bool isUnivalTree(struct TreeNode* root){ }
解析代码：
bool isUnivalTree(struct TreeNode* root) { if (root == NULL)//空结点就返回true { return true; } if (root->left && root->val != root->left->val) { return false; } if (root->right && root->val != root->right->val) { return false; } //走到这就是结点的左右孩子存在时的值都等于父亲的值（符合单值二叉树） //返回这个左子树和右子树都是单值二叉树（只要有一个不是就是false） return isUnivalTree(root->left) && isUnivalTree(root->right); }
104. 二叉树的最大深度
难度简单
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ int maxDepth(struct TreeNode* root){ }
解析代码：
/*int maxDepth(struct TreeNode* root) { if (root == NULL) { return 0; } return maxDepth(root->left) > maxDepth(root->right) ? maxDepth(root->left) + 1 : maxDepth(root->right) + 1; }*/ //这样写会有重复的递归计算， 优化： int maxDepth(struct TreeNode* root) { if (root == NULL) { return 0; } int leftDepth = maxDepth(root->left); int rightDepth = maxDepth(root->right); return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1; }
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
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ bool isBalanced(struct TreeNode* root){ }
解析代码：
int maxDepth(struct TreeNode* root) { if (root == NULL) { return 0; } int leftDepth = maxDepth(root->left); int rightDepth = maxDepth(root->right); return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1; } bool isBalanced(struct TreeNode* root){ if(root == NULL) { return true; } //当前树的左右子树高度差不大于1，并且左右子树本身也是平衡树。 return (abs(maxDepth(root->left) - maxDepth(root->right)) <= 1) && isBalanced(root->left) && isBalanced(root->right); }
数据结构与算法⑮(第四章_下)二叉树OJ(力扣:144,965,104,110,226,100,101,572)（下）：https://developer.aliyun.com/article/1513526
