随想录刷题笔记 —二叉树篇7 617合并二叉树 700二叉搜索树中的搜索 98验证二叉搜索树

本文主要是介绍随想录刷题笔记 —二叉树篇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;}
}