【ブラシでカードを打つ】day 11-二叉樹
今から毎日少なくとも一つの問題を書きます.タイトル:lintcode
一部のテーマのリンクが開かないので、権限が必要です.じゃ、皆さんは九章アルゴリズムの参考答案の中で探してみます.
Insert Node in a Binary Search Tree
リンクの難易度:easyアルゴリズム:二分割法
問題を解く構想は一定の木の葉っぱのノードに挿入する.targetがノード値より大きい場合、右側のツリーを検索します.さもなければ、左のツリーを検索します.nullを検索すると、挿入できる場所が見つかるということです.挿入先の親ノードを格納します.この親ノードがtargetより大きい場合、targetは親ノードの左ノードであり、そうでなければ右ノードである.
時間複雑度:O(logn)空間複雑度:O(1)
法を解く
リンクの難易度:ハーレーアルゴリズム:二分割法
問題を解くには、まず、targetのノードとその親ノードを探します.その後、タレッジノードは、左サブツリーの最大値または右サブツリーの最小値で置換される.なお、タレットノードがルートノードである場合、ルートノードには親ノードがないので、ルートノードに親ノードを作成します.具体的な手順ルートノードから出発し、タリゲトvalueがルートノードの値より大きい場合、右側のツリーが検索を継続する.小さい場合は、左のツリーを検索します.等しい場合、検索を停止し、現在のノードの親ノード に戻る.は、target左サブツリーの最大値をtargetノードに置き換えると仮定し、右サブツリーの最小値を用いても良いし、その1つだけを考慮しても良い.もしtargetの左ノードがnullであるならば、parentは直接にtargetの右ノードを指す.そうでなければ、ターゲットの左サブツリーで最大ノードとその親ノード、つまり一番右側を検索します.見つかったら、親の値を最大ノードの左ノードに向け(右ノードがすでに空いているので)、タレットを最大ノードに置き換える.最大ノードの左右ノードを介して、targetの左右ノードを指す. 時間複雑度:O(logn)、検索ノードが2分で行う、O(logn).ノードを削除するのも二点です.実はずっと右に行きます.O(logn)空間複雑度:O(1)
法を解く
一部のテーマのリンクが開かないので、権限が必要です.じゃ、皆さんは九章アルゴリズムの参考答案の中で探してみます.
Insert Node in a Binary Search Tree
リンクの難易度:easyアルゴリズム:二分割法
問題を解く構想は一定の木の葉っぱのノードに挿入する.targetがノード値より大きい場合、右側のツリーを検索します.さもなければ、左のツリーを検索します.nullを検索すると、挿入できる場所が見つかるということです.挿入先の親ノードを格納します.この親ノードがtargetより大きい場合、targetは親ノードの左ノードであり、そうでなければ右ノードである.
時間複雑度:O(logn)空間複雑度:O(1)
法を解く
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/*
* @param root: The root of the binary search tree.
* @param node: insert this node into the binary search tree
* @return: The root of the new binary search tree.
*/
public TreeNode insertNode(TreeNode root, TreeNode node) {
// write your code here
if(root == null){
return node;
}
TreeNode curr = root;
TreeNode last = null;
while(curr != null){
last = curr;
if(curr.val > node.val){
curr = curr.left;
}else{
curr = curr.right;
}
}
if(last != null){
if(last.val > node.val){
last.left = node;
}else{
last.right = node;
}
}
return root;
}
}
リンクの難易度:ハーレーアルゴリズム:二分割法
問題を解くには、まず、targetのノードとその親ノードを探します.その後、タレッジノードは、左サブツリーの最大値または右サブツリーの最小値で置換される.なお、タレットノードがルートノードである場合、ルートノードには親ノードがないので、ルートノードに親ノードを作成します.具体的な手順
法を解く
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/*
* @param root: The root of the binary search tree.
* @param value: Remove the node with given value.
* @return: The root of the binary search tree after removal.
*/
public TreeNode removeNode(TreeNode root, int value) {
// write your code here
TreeNode dummy = new TreeNode(0);
dummy.left = root;
TreeNode parent = findNode(dummy, root, value);
TreeNode target;
if(parent.left != null && parent.left.val == value){
target = parent.left;
}else if(parent.right != null && parent.right.val == value){
target = parent.right;
}else{
return dummy.left;
}
// System.out.printf("%d %d
", parent.val, target.val);
//replace target node
deleteNode(parent, target);
return dummy.left;
}
private TreeNode findNode(TreeNode parent, TreeNode node, int value){
if(node == null){
return parent;
}
if(node.val == value){
return parent;
}
while(node != null){
if(node.val > value){
parent = node;
node = node.left;
}else if(node.val < value){
parent = node;
node = node.right;
}else{
break;
}
}
return parent;
}
private void deleteNode(TreeNode parent, TreeNode node){
if(node.left == null){
if(parent.left == node){
parent.left = node.right;
}else{
parent.right = node.right;
}
}
else{
//replace node with the largest value on the left
//node 3
//parent 5
TreeNode tmp = node.left; //2
TreeNode father = node; //3
while(tmp.right != null){
father = tmp;
tmp = tmp.right;
}
//remove the largest value
if(father.left == tmp){
father.left = tmp.left; //null
}else{
father.right = tmp.left;
}
// System.out.printf("%d %d
",parent.left.val, node.val);
if(parent.left == node){
System.out.print(tmp.val);
parent.left = tmp; //2
}else{
parent.right = tmp;
}
tmp.left = node.left; //null
tmp.right = node.right; //4
}
}
}