随想录刷题笔记 —二叉树篇9 236二叉树最近公共祖先 235二叉搜索树最近公共祖先 701二叉搜索树插入操作

本文主要是介绍随想录刷题笔记 —二叉树篇9 236二叉树最近公共祖先 235二叉搜索树最近公共祖先 701二叉搜索树插入操作，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

236二叉树最近公共祖先

后序遍历：递归到头，或者该结点是p或q那么则返回该结点。

如果左和右返回的都不是空，那么此节点就是深度最大的公共结点。

如果左是空，那么就返回右。

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null || root == p || root == q){return root;}TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);if(left!=null && right!=null){return root;}if(left==null){return right;}else{return left;}}}

235二叉搜索树最近公共祖先

跟上一题思路一致

由于是二叉搜索树因此可以通过值来减少不必要判断。

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null || root == p || root == q){return root;}TreeNode left = null;TreeNode right = null;if (root.val>p.val||root.val>q.val){left = lowestCommonAncestor(root.left, p, q);}if (root.val<p.val||root.val<q.val){right = lowestCommonAncestor(root.right, p, q);}if(left!=null && right!=null){return root;}if(left==null){return right;}else{return left;}}
}

701二叉搜索树插入操作

递归查找，找到合适位置的空结点插入

class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {if (root==null){return new TreeNode(val, null, null);}TreeNode node = root;while (node!=null){if (val<node.val){if (node.left==null){node.left = new TreeNode(val, null, null);break;}node = node.left;}if (val>node.val){if (node.right==null){node.right = new TreeNode(val, null, null);break;}node = node.right;}}return root;}
}