654.最大二叉树

思路：

根据昨天做的前序+中序or中序＋后序的思路进行做题。1.判断数组是否为空 2.找到数组中的最大值和其位置 3.根据数组最大值构造root根节点 4.根据其位置区分左右区间 5.对左右区间进行左节点和右节点的遍历构造

看视频：

if(nums.size()==1) return root;

如果不每次构造新vector<int>，效率会提高。

 617.合并二叉树

思路：

终止条件：

if(root1==NULL && root2==NULL)return NULL;

构造根节点；

分成三种情况讨论：

root1 root2都不为空：root->val=两节点数值相加，左右节点则正常遍历root1和root2的左右节点

root1为空root2不为空：root->val=root2，左右节点遍历中的root1改为NULL；

root1不为空root2为空：root->val=root1，左右节点遍历中的root2改为NULL；

最后return root；

看视频后：

1.终止条件可改成

if(root1==NULL) return root2;

if(root2==NULL) return root1;

2.可以不额外构造树，在root1的基础上判断，在root1上操作即可；

700.二叉搜索树中的搜索

思路：

终止条件：root==NULL

分情况讨论：

相等返回root，val小于root->val继续查找左子树，大于查找右子树

看视频后：

这题迭代法也比较简单。

98.验证二叉搜索树

思路：

掉进陷阱里了：只判断了左节点比根节点小和右节点比根节点大

看视频后：

使用中序遍历，二叉搜索树在中序遍历的情况下是一个有序数组。

1. 新建函数，使用一个数组记录下二叉搜索树在中序遍历下的元素，再在原函数对数组内部顺序进行判断

2. 中序遍历过程中判断：

用双指针则不需要担心初始化的最小数和树中最小元素的比较问题

用pre记录前一个节点

中止条件：root==NULL

遍历顺序：左中右

左和右都是记录左子树和右子树的遍历情况

中：判断pre不为空且pre的值是否大于等于root的值，是则返回false

将pre=root

最后return left&&right;