随想录刷题笔记 —二叉树篇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;}
}收获
后序遍历加回溯=逆序查找