不同的二叉搜索树

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

• 思路分析：
  遍历每个整数i作为根节点，由二叉搜索定义知，则左子树包含[1,2,...,i-1]，右子树包含[i+1,i+2,......,n]，接着我们以同样的方式递归建立左右子树。
  • 令build(i),即为以整数i作为根节点的所建立的二叉搜索树；

则有如下：
build(i)=build(i-1)+build(n-i);
上式显然涉及重复计算，故可使用记忆化降低复杂度

验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。

节点的右子树只包含大于当前节点的数。

所有左子树和右子树自身必须也是二叉搜索树。

• 思路分析：

由题意知，当前节点root，其存在一个范围限制root->val的大小，故可设置一个递归方法check(root,low,high),其中有low<root->val<high,所有节点满足上述条件才为二叉搜索树。

• 递归结束判断
  • 若root==nullptr,显然满足上述条件，return true;
  • 若root不满足上述区间，则return false;
  • 递归的检验root->left、root->right

对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

1

/ \

2 2

/ \ / \

3 4 4 3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的

1

/ \

2 2

\ \

3 3

思路分析

对于一个二叉树镜像对称，即其左右子树是完全镜像翻转的，故我们可以设置checkMirror(p,q)，两个指针同时移动来遍历左右子树，以判断其是否是镜像翻转。

• 递归思路
  • 递归结束条件
    • 若p==nullptr==q,返回true;
    • 若p和q仅有一个为nullptr，返回false;
    • 若p->val!=q->val，显然非镜像，返回false;
  • 递归判断pq的左右子树，即
    • check(p->left,q->right) && check(p->right,q->left)

      递归改迭代

      首先我们引入一个队列，这是把递归程序改写成迭代程序的常用方法。首先将根节点入队两次，每次比较涉及队列中相邻的两个节点。

      1. 队列中出队p、q,并判断p、q是否相等
      2. 相等下，将p->left,q->right入队
      3. 将p->right,q->left入队
      4. 重复上述步骤直到队列为空