关于java:二叉树题型框架5

判断BST的非法

最容易想到的就是套用咱们的先序遍历框架

boolean isValidBST(TreeNode root){
if(root==null){
return true;
}
if(root.left!=null&&root.val<=root.left.val){
return false;
}
if(root.right!=null&&root.val>=root.right.val){
return false;
}
return isValidBST(root.left)&&isValidBST(root.right);
}

减少参数列表,在参数中携带额定信息,通过辅助函数将下层节点的束缚传递下来

boolean isValidBST(TreeNode root,TreeNode min,TreeNode max){
if(root==null){
return true;
}

boolean isValidBST(TreeNode root,TreeNode min,TreeNdoe max){
//base case
if(root==null){
return true;
}
//若root.val不合乎max和min的限度,阐明不是非法BST
if(min!=null&&root.val<=min.val) return false;
if(max!=null&&root.val>=max.val)return false;
//限定左子树的最大值是root.val，右子树的最小值是root.val
return isValidBST(root.left,min,root)&&isValidBST(root.right,root,max);
}

在BST中搜寻一个数

这个比较简单，间接放框架代码

void BST(TreeNode root,int target){
if(root.val==target){
//找到指标,做点什么
}
if(root.val<target){
BST(root.right,target);
}
if(root.val>target){
BST(root.left,target);
}
}

在BST中插入一个数

一旦波及[改],函数就要返回TreeNode类型,并且对递归调用的返回值进行接管

TreeNode insertIntoBST(TreeNode root,int val){
//找到空地位插入新节点
if(root==null){
return new TreeNode(val);
}
//if(root.val==val)
//BST中个别不会插入已存在的元素
if(root.val<val){
root.right=insertIntoBST(root.right,val);
}
if(root.val>val){
root.left=insertIntoBST(root.left,val);
}
return root;
}

在BST中删除一个数(重点)

TreeNode deleteNode(TreeNdde root,int key){
if(root.val==key){
//找到啦，进行删除
}else if(root.val>key){
//去左子树找
root.left=deleteNode(root.left,key);
}else if(root.val<key){
//去右子树找
root.right=deleNode(root.right,key);
}
return root;
}

思考删除节点时咱们须要干什么？
状况1:A恰好是末端节点,两个节点都为空,那么它能够当场逝世了

if(root.left==null&&root.right==null){
return null;
}

状况2:A只有一个非空子节点,那么它要让这个孩子接替本人的地位

if(root.left==null) return root.right;
if(root.right==null) return root.left;
状况3:A有两个子节点，为了不毁坏BST的性质，A必须找到左子树中最大的那个节点，或者右子树中最小的那个节点来接替本人。

if(root.left!=null&&root.right!=null){
//找到右子树的最小节点
TreeNode minNode=getMin(root.right);
//把root改成minNode
root.val=minNode.val;
//删除minNode
root.right=deleteNode(root.rigth,minNode.val);
}

框架代码

TreeNode deleteNode(TreeNode root,int key){
if(root==null){
return null;
}
if(root==key){
//这两个if把状况１和２都正确地解决了
if(root.left==null) return right;
if(root.right==null) return left;
//解决状况3
TreeNode minNode=getMin(root.right,minNode.val);
root.val=minNdode.val;
root.right=deleteNode(root.right,minNode.val);
}else if(root.val>key){
root.let=deleteNode(root.left,key);
}else if(root.val<key){
root.right=deleteNode(root.right,key);
}
return root;
}

TreeNdoe getMin(TreeNode node){
//BST最右边的就是最小的
while(node.left!=null){
node=node.left;
}
}

最初总结
1.如果以后节点会对上面的子节点有整体影响，能够通过辅助函数增长参数列表
2.BST框架代码

void BST(TreeNode root, int target) {
    if (root.val == target)
        // 找到指标，做点什么
    if (root.val < target) 
        BST(root.right, target);
    if (root.val > target)
        BST(root.left, target);
}