珠海建设局网站首页,wordpress会员时间,做旅游攻略网站好,农产品品牌推广方案首先需要认识什么是二叉搜索树#xff0c;可以进入百度词条https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/7077855?fraladdin
一定要注意题目要求算法时间复杂度是O(h)。
递归方法#xff1a;
/*** Definition for a binary tree node.* …
首先需要认识什么是二叉搜索树可以进入百度词条https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/7077855?fraladdin
一定要注意题目要求算法时间复杂度是O(h)。
递归方法
/*** 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 deleteNode(TreeNode root, int key) {if (root null)return null;if (key root.val) {// 1.leafif (root.left null root.right null) {return null;} else if (root.left null) { // 2.left is nullreturn root.right; } else if (root.right null) { // 3.right is nullreturn root.left;} else { // 4.left and right are not nullTreeNode rightTreeMin root.right;while (rightTreeMin.left ! null) {rightTreeMin rightTreeMin.left; //找到右子树中最小的叶子节点}root.val rightTreeMin.val;root.right deleteNode(root.right, rightTreeMin.val);//继续向当前root节点的右子树递归此时的key变成了rightTreeMin.val以达到去删除这个最小叶子节点的目的}} else if (key root.val) {root.right deleteNode(root.right, key);} else { //keyroot.valroot.left deleteNode(root.left, key);}return root;}
}参考博文LeetCode 删除二叉搜索树中的节点450题递归与非递归
