构造二叉树昨天做了105/106今天继续LC 654 · 最大二叉树思路前序递归每次找最大值做根。找数组中最大值的下标左边的子数组构造左子树右边构造右子树递归下去。和105/106构造二叉树是同一个套路——构造类题目天然是前序因为必须先确定根节点才能划分左右子树。LC 617 · 合并二叉树思路同时递归两棵树。两个指针同步往下走对应节点值相加。边界情况一个为空就直接返回另一个不用继续递归。可以复用 t1 的节点结构也可以新建节点前者省空间。同时操作两棵树第一次见但递归结构和单棵树完全一样适应一下就好。LC 700 · 二叉搜索树中的搜索思路利用 BST 性质不用遍历全树。BST 的核心性质左子树所有节点 根 右子树所有节点。搜索时比较目标值和当前节点小了往左走大了往右走等于就返回。最坏 O(h)平衡时 O(logn)比普通二叉树搜索高效得多。迭代版比递归版更直观while 循环一路走下去就行。LC 98 · 验证二叉搜索树思路中序遍历结果应该严格递增。BST 的中序遍历一定是升序序列所以中序遍历过程中记录上一个节点的值当前值必须严格大于它否则不合法。陷阱在这里不能只比较左子节点 根 右子节点比如根节点右子树里的最左节点也必须大于根局部合法不代表整体合法。中序遍历天然绕过这个坑是处理BST问题的标配思路。今天最重要的两点构造树用前序验证/操作BST用中序。BST专题正式开始后面的题都要先想到中序遍历是有序的这个性质能省很多力气。明天继续