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

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*（思路：对于一个结点，只要其左子树出现p或q，或右子树出现p或q，那么该节点就是节点p和q的最近公共                    祖先；*如果递归遍历遇到q，就将q返回，遇到p就将p返回，那么如果左右子树的返回值都不为空，说明此时的中节 点，一定是q和p的最近祖先。**/
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//递归结束条件if(root==p||root==q||root==null){return root;}//左TreeNode left=lowestCommonAncestor(root.left,p,q);//右TreeNode right=lowestCommonAncestor(root.right,p,q);//中if(left!=null&&right!=null){return  root;  //最近公共祖先}else if(left==null&&right!=null){return right;   // 若找到一个节点  继续向上返回直到根节点} else if (left != null && right == null) {return left;   // 若找到一个节点  继续向上返回直到根节点}else {return null;   //没找到结点}}
}

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

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

迭代

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//迭代while (root!=null){if(root.val>=p.val&&root.val<=q.val||root.val<=p.val&&root.val>=q.val||root==null){return root;}if(root.val>p.val&&root.val>q.val){root=root.left;}else if(root.val<p.val&&root.val<q.val){root=root.right;}}return root;}
}

递归

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//递归if(root==null){return null;}if(root.val>p.val&&root.val>q.val){TreeNode left=lowestCommonAncestor1(root.left,p,q);if(left!=null){return left;}}if(root.val<p.val&&root.val<q.val){TreeNode right=lowestCommonAncestor1(root.right,p,q);if(right!=null){return right;}}return root;}
}

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

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回 任意有效的结果 。

/*** 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 {public TreeNode insertIntoBST(TreeNode root, int val) {//递归终止条件，当遍历到空节点时，就是要插入节点的时候，返回要插入的节点if(root==null){TreeNode node=new TreeNode(val);return node;}if(root.val<val){root.right=insertIntoBST(root.right,val);}if(root.val>val){root.left=insertIntoBST(root.left,val);}return  root;}
}

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

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；
如果找到了，删除它。

/*** 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;*     }* }* （思路：删除二叉树中节点可以分为以下几种情况：* 		1.未找到要删除的节点* 		2.找到要删除的节点：* 			2.1	删除节点为叶子结点---直接删除* 			2.2 删除节点不是叶子结点，但其左孩子为空，右孩子不为空---直接让其父节点指向该节点的右孩子* 			2.3	删除节点不是叶子结点，但其右孩子为空，左孩子不为空---直接让其父节点指向该节点的左孩子* 			2.4 删除节点不是叶子结点，且左右孩子均不为空：* 				右孩子继位，将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上*/
class Solution {public TreeNode deleteNode(TreeNode root, int key) {//递归终止条件:遇到空直接返回（没找到要删除的节点if(root==null){return null;}//找到要删除的节点:返回删除后的根节点if(root.val==key){//1.删除节点为叶子结点if(root.left==null&&root.right==null){return null;} else if (root.left!=null&&root.right==null) { //2.删除节点左孩子不为空return root.left;} else if (root.right != null&&root.left==null) { //3.删除节点右孩子不为空return root.right;}else{  //4.删除节点左右孩子均不为空TreeNode node=root.right;while(node.left!=null){node=node.left;    //找到右子树的最左边的节点}node.left=root.left;   //把要删除的节点（root）左子树放在cur的左孩子的位置return root.right;}}if(root.val>key){root.left=deleteNode(root.left, key);}if(root.val<key){root.right=deleteNode(root.right,key);}return root;}
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/104973.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！