乐趣区

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

jiezi

判断 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 把状况1和2都正确地解决了
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);
}
退出移动版