随想录刷题笔记 —二叉树篇7 617合并二叉树 700二叉搜索树中的搜索 98验证二叉搜索树
617合并二叉树
递归：如果root1和root2其中有一个为空，则将另一个的结点直接赋值即可——将该节点和子树都直接赋值过去了。
如果都不是空，就需要重新建立一个结点再进入递归。
class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1==null){return root2;}if(root2==null){return root1;}TreeNode node = new TreeNode();node.val = root1.val+root2.val;node.left = mergeTrees(root1.left, root2.left);node.right = mergeTrees(root1.right, root2.right);return node;}
}700二叉搜索树中的搜索
二叉查找：如果节点值大于val则向左查找，小于则向右查找
解法一：迭代法
class Solution {public TreeNode searchBST(TreeNode root, int val) {while (root!=null){if (root.val==val){return root;}if (root.val<val){root = root.right;}else {root = root.left;}}return null;}
}解法二：递归
class Solution {public TreeNode searchBST(TreeNode root, int val) {if (root==null||root.val==val){return root;}if (root.val<val){return searchBST(root.right, val);}else {return searchBST(root.left, val);}}
}98验证二叉搜索树
注意判断结点值需要大于左子树的最大值，右子树需要大于节点值，因此就可以判断左>中>右
递归：设置maxBST值，标记当前左边部分的最大值。
使用中序遍历，因此maxBST的值顺序为左中右。
class Solution {TreeNode maxBST = null;public boolean isValidBST(TreeNode root) {if (root.left!=null){if (root.val<=root.left.val||!isValidBST(root.left)){return false;}}if (maxBST!=null&&maxBST.val>=root.val){return false;}maxBST = root;if (root.right!=null){return root.val < root.right.val && isValidBST(root.right);}return true;}
}收获
二叉搜索树是左子树全部小于根节点小于右子树，而不只是单纯的左孩子小于根节点小于右孩子