二叉树习题其五【力扣】【算法学习day.12】

前言

书接上篇文章二叉树习题其四，这篇文章我们将基础拓展

###我做这类文档一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

---

习题

1.二叉树的最近公共祖先

题目链接:236. 二叉树的最近公共祖先 - 力扣（LeetCode）

题面:

基本分析:如果一个节点的左右子树含有目标值，那么这个节点就是祖先，如果只有左/右子树含有，那这个就不是祖先

代码:

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {TreeNode res;public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {recursion(root,p.val,q.val);return res;}public int recursion(TreeNode node,int a,int b){if(node==null)return 0;int c = node.val==a|node.val==b?1:0;int left = recursion(node.left,a,b);int right = recursion(node.right,a,b);if(c+left+right==2)res = node;return c+left+right==0?0:1;}
}

---

2.二叉搜索树中的插入操作

题目链接:701. 二叉搜索树中的插入操作 - 力扣（LeetCode）

题面:

基本分析:根据二叉搜索树的规则一直遍历到空值然后插入即可 

代码:

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int res;TreeNode flag;public TreeNode insertIntoBST(TreeNode root, int val) {// System.out.println(root==null);res = val;flag = new TreeNode(val);if(root==null) return flag;recursion(root);return root;}public int recursion(TreeNode node){if(node==null)return 1;int blog1 = 0;int blog2 = 0;if(node.val<res)blog1 = recursion(node.right);if(node.val>res)blog2 = recursion(node.left);if(blog1==1)node.right = flag;else if(blog2==1)node.left = flag;return 0;}
}

---

 

3.删除二叉搜索树中的节点

题目链接:450. 删除二叉搜索树中的节点 - 力扣（LeetCode）

题面:

基本分析:如果遍历到要删除的节点，分情况的讨论，如果左右节点都是空，就返回null，如果左/右有一个为空，就返回右/左，如果左右都不为空，则需要将子树拼接，具体看代码 

代码:

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int target;public TreeNode deleteNode(TreeNode root, int key) {target = key;if(root==null)return null;return  recursion(root);}public TreeNode recursion(TreeNode node){if(node==null)return null;if(node.val==target){if(node.left==null)return node.right;if(node.right==null)return node.left;TreeNode c = node.left;while(c.right!=null)c = c.right;c.right = node.right;return node.left;}else{if(node.val>target)node.left = recursion(node.left);else node.right = recursion(node.right);}return node;}}

---

后言

上面是二叉树的部分习题，下一篇会讲解二叉树的其他相关力扣习题，希望有所帮助，一同进步，共勉！