华为云建设网站,江门网站建设junke100,培训行业seo整站优化,wordpress 新安装 慢前言
书接上篇文章二叉树习题其四#xff0c;这篇文章我们将基础拓展
###我做这类文档一个重要的目的还是给正在学习的大家提供方向#xff08;例如想要掌握基础用法#xff0c;该刷哪些题#xff1f;#xff09;我的解析也不会做的非常详细#xff0c;只会提供思路和一…前言
书接上篇文章二叉树习题其四这篇文章我们将基础拓展
###我做这类文档一个重要的目的还是给正在学习的大家提供方向例如想要掌握基础用法该刷哪些题我的解析也不会做的非常详细只会提供思路和一些关键点力扣上的大佬们的题解质量是非常非常高滴 习题
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(nodenull)return 0;int c node.vala|node.valb?1:0;int left recursion(node.left,a,b);int right recursion(node.right,a,b);if(cleftright2)res node;return cleftright0?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(rootnull);res val;flag new TreeNode(val);if(rootnull) return flag;recursion(root);return root;}public int recursion(TreeNode node){if(nodenull)return 1;int blog1 0;int blog2 0;if(node.valres)blog1 recursion(node.right);if(node.valres)blog2 recursion(node.left);if(blog11)node.right flag;else if(blog21)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(rootnull)return null;return recursion(root);}public TreeNode recursion(TreeNode node){if(nodenull)return null;if(node.valtarget){if(node.leftnull)return node.right;if(node.rightnull)return node.left;TreeNode c node.left;while(c.right!null)c c.right;c.right node.right;return node.left;}else{if(node.valtarget)node.left recursion(node.left);else node.right recursion(node.right);}return node;}} 后言
上面是二叉树的部分习题下一篇会讲解二叉树的其他相关力扣习题希望有所帮助一同进步共勉
