树的习题（404，98，110）（前中后序遍历）

第一个题404：
给定二叉树的根节点 root ，返回所有左叶子之和。
输入: root = [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
/**

• Definition for a binary tree node.

• struct TreeNode {

• int val;
  

• struct TreeNode *left;
  

• struct TreeNode *right;
  

• };
  /
  int sumOfLeftLeaves(struct TreeNode root)
  {
  if(root == NULL)
  {
  return 0;
  }
  //后序遍历，这里先写整体出口，从根开始遍历
  int sum = 0;

  if(root->left != NULL
  && root->left->left == NULL
  && root->left->right == NULL)
  {
  sum += root->left->val;
  }
  //这里是判断根是左叶子的情况，也就是根有左儿子，然后左儿子作为叶子节点，没有左右儿子则相加
  sum += sumOfLeftLeaves(root->left);

  sum += sumOfLeftLeaves(root->right);
  //相加左儿子的左节点和右儿子的左节点
  return sum;
  }
  其实后序遍历递归的本质还是：先写出口，之后判断最终递归的情况，然后不断递归往下传，之后再一层层return回来

第二个题101：
给定一个二叉树，判断它是否是 平衡二叉树 ：

输入：root = [3,9,20,null,null,15,7]
输出：true

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

输入：root = []
输出：true

/**

• Definition for a binary tree node.
• struct TreeNode {

• int val;
  

• struct TreeNode *left;
  

• struct TreeNode *right;
  

• };
  */
  #define MAX(a,b) ((a)>(b)?(a):(b))

int getHeight(struct TreeNode* root)
{
if(root == NULL)
{
return 0;
}
//还是先递归出口，但是这里要想清楚左高度是需要在这里往下递归左边的
int lefthight = getHeight(root->left);
//因为这里如果不在这里写，第一次递归lefthight就没有定义了
if(lefthight == -1)
{
return -1;
}

int righthight = getHeight(root->right);

if(righthight == -1)
{
    return -1;
}

if(abs(righthight - lefthight) >= 2)
{
    return -1;
}

//这里相当于绝对值差大于等于2，就把-1一直往上传，直到退出，如果不大于等于二，就去取最大值然后加1（根的高度）表示深度
return MAX(lefthight,righthight) + 1;
}

bool isBalanced(struct TreeNode* root)
{
return getHeight(root) != -1;
}

第三个题98：
二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

节点的左子树只包含 严格小于 当前节点的数。
节点的右子树只包含 严格大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

输入：root = [2,1,3]
输出：true

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

/**

• Definition for a binary tree node.
• struct TreeNode {

• int val;
  

• struct TreeNode *left;
  

• struct TreeNode *right;
  

• };
  */

#include <stdbool.h>
#include <limits.h>
//这里要传入一个root的参数的话不好做，因为怎么说呢，就是如果保证root->val<=root->left->val ||root->val>=root->left->val 之后判false并不可取
首先就是一个问题，有可能root没有左右儿子，所以也就不存在左右的val，这个得提前判断Null之后修正好解决
但是还有一个问题就是，如果满足这样的条件也可能不是二叉搜索树，诸如，根节点是3，右儿子是4，然后右儿子又有左右两个儿子2和5，2<4<5但是会发现，2比3小，也就是孙子节点和爷爷节点之间也也还有关系，不是二叉搜索树，所以我们最好传入一个范围最好，表示比较的范围
bool check(struct TreeNode* root, long long low, long long high)
{
if(root == NULL)
{
return true;
}

if(root->val <= low || root->val >= high)
{
    return false;
}

return check(root->left, low, root->val)
    && check(root->right, root->val, high);

}
//右节点相当于爷爷作为low，下一次的儿子作为high，左节点相当于爷爷作为high，下一次的儿子作为low，这样相当于是左右都走，如果一直往左或者右走，就是无穷
//因为这里是针对的根比较而言，也就是比较根对应节点卡住的范围，不涉及他的儿子比较，所以是前序遍历

bool isValidBST(struct TreeNode* root)
{
return check(root, LLONG_MIN, LLONG_MAX);
}

再次解释这里是前序遍历，也就是说，每次使用的范围是根据上一次保留下来的范围，如果是左节点的话，low作为下界，上一次根的val作为上界，

这里看一下灵神的中序和后序遍历做这道题

方法二：中序遍历
本题是二叉搜索树，中序遍历是自然的做法。

中序遍历时，可以把二叉搜索树看成一个有序数组。

怎么判断一个数组是有序数组？比较相邻元素的大小即可。

问：如何证明，如果二叉树的中序遍历是严格递增的，那么二叉树一定是二叉搜索树？

答：已知条件为，中序遍历是严格递增的。我们要证明这棵二叉树是二叉搜索树。对于这棵二叉树的任意节点 x，中序遍历中的在 x 左边的点都是遍历过的点，这包含 x 的左子树，所以 x 的左子树的节点值都严格小于 x 的节点值。中序遍历中的在 x 右边的点都是未遍历过的点，这包含 x 的右子树，所以 x 的右子树的节点值都严格大于 x 的节点值。所以这棵二叉树的每个节点都满足二叉搜索树的性质，所以这棵二叉树是二叉搜索树。

bool dfs(struct TreeNode* root, long long* pre) {
if (root == NULL) {
return true;
}
if (!dfs(root->left, pre)) { // 左
return false;
}
if (root->val <= *pre) { // 中
return false;
}
pre = root->val;
return dfs(root->right, pre); // 右
}
//第一次先定义pre是LLONG_MIN，然后根据中序遍历依次返回，一开始是最底下，所以直接就是NULL之后读了上一层的val就返回，然后根据左中右的顺序，把每次上一个节点的值作为pre，然后当前节点比较，比如说先最开始左，之后中，中间把自己的节点val改成pre，再给右边，再改pre，之后再回到左边
bool isValidBST(struct TreeNode root) {
long long pre = LLONG_MIN;
return dfs(root, &pre);
}
复杂度分析
时间复杂度：O(n)，其中 n 为二叉搜索树的节点个数。
空间复杂度：O(n)。最坏情况下，二叉搜索树退化成一条链（注意题目没有保证它是平衡树），因此递归需要 O(n) 的栈空间。

方法三：后序遍历
dfs 返回子树的最小值和最大值，供上面的节点判断是否为二叉搜索树。

#define MIN(a, b) ((b) < (a) ? (b) : (a))
#define MAX(a, b) ((b) > (a) ? (b) : (a))

typedef struct {
long long min; // 子树最小值
long long max; // 子树最大值
} Pair;

Pair dfs(struct TreeNode* node) {
if (node == NULL) {
return (Pair) {LLONG_MAX, LLONG_MIN};
}
Pair l = dfs(node->left);
Pair r = dfs(node->right);
long long x = node->val;
// 也可以在递归完左子树之后立刻判断，如果发现不是二叉搜索树，就不用递归右子树了
if (x <= l.max || x >= r.min) {
return (Pair) {LLONG_MIN, LLONG_MAX};
}
return (Pair) {MIN(l.min, x), MAX(r.max, x)};
}

bool isValidBST(struct TreeNode* root) {
return dfs(root).max != LLONG_MAX;
}

复杂度分析
时间复杂度：O(n)，其中 n 为二叉搜索树的节点个数。
空间复杂度：O(n)。最坏情况下，二叉搜索树退化成一条链（注意题目没有保证它是平衡树），因此递归需要 O(n) 的栈空间。

前序遍历在某些数据下不需要递归到叶子节点就能返回（比如根节点左儿子的值大于根节点的值，左儿子就不会继续往下递归了），而中序遍历和后序遍历至少要递归到一个叶子节点。从这个角度上来说，前序遍历是最快的。
中序遍历很好地利用了二叉搜索树的性质，使用到的变量最少。
后序遍历的思想是最通用的，即自底向上计算子问题的过程。想要学好动态规划的话，请务必掌握自底向上的思想。