Chapter 05 BST predecessor and successor algo optimized.

liuyubobobo · liuyubobobo · commit a0abfbc9514d · 2017-11-14T19:12:35.000-08:00
diff --git a/05-Binary-Search-Tree/Course Code (C++)/Optional-03-Predecessor-and-Successor/main.cpp b/05-Binary-Search-Tree/Course Code (C++)/Optional-03-Predecessor-and-Successor/main.cpp
@@ -440,21 +440,19 @@ class BST{
         if(node->key == key)
             return NULL;
 
-        Node* maxNode;
         if(key < node->key)
             // 如果当前节点大于key, 则当前节点不可能是比key小的最大值
             // 向下搜索到的结果直接返回
             return predecessorFromAncestor(node->left, key);
         else{
             assert(key > node->key);
             // 如果当前节点小于key, 则当前节点有可能是比key小的最大值
-            // 向下搜索结果存储到maxNode中
-            maxNode = predecessorFromAncestor(node->right, key);
-            if(maxNode)
-                // maxNode和当前节点node取最大值返回
-                return maxNode->key > node->key ? maxNode : node;
+            // 向右继续搜索, 将结果存储到tempNode中
+            Node* tempNode = predecessorFromAncestor(node->right, key);
+            if(tempNode)
+                return tempNode;
             else
-                // 如果maxNode为空, 则当前节点即为结果
+                // 如果tempNode为空, 则当前节点即为结果
                 return node;
         }
     }
@@ -466,26 +464,25 @@ class BST{
         if(node->key == key)
             return NULL;
 
-        Node* minNode;
         if(key > node->key)
             // 如果当前节点小于key, 则当前节点不可能是比key大的最小值
             // 向下搜索到的结果直接返回
             return successorFromAncestor(node->right, key);
         else{
             assert(key < node->key);
             // 如果当前节点大于key, 则当前节点有可能是比key大的最小值
-            // 向下搜索结果存储到minNode中
-            minNode = predecessorFromAncestor(node->left, key);
-            if(minNode)
-                // minNode和当前节点node取最小值返回
-                return minNode->key < node->key ? minNode : node;
+            // 向左继续搜索, 将结果存储到tempNode中
+            Node* tempNode = predecessorFromAncestor(node->left, key);
+            if(tempNode)
+                return tempNode;
             else
-                // 如果minNode为空, 则当前节点即为结果
+                // 如果tempNode为空, 则当前节点即为结果
                 return node;
         }
     }
 };
 
+
 void shuffle( int arr[], int n ){
 
     srand( time(NULL) );
diff --git a/05-Binary-Search-Tree/Course Code (Java)/Optional-03-Predecessor-and-Successor/src/bobo/algo/BST.java b/05-Binary-Search-Tree/Course Code (Java)/Optional-03-Predecessor-and-Successor/src/bobo/algo/BST.java
@@ -423,21 +423,19 @@ Node predecessorFromAncestor(Node node, Key key){
         if(node.key.compareTo(key) == 0)
             return null;
 
-        Node maxNode;
         if(key.compareTo(node.key) < 0)
             // 如果当前节点大于key, 则当前节点不可能是比key小的最大值
             // 向下搜索到的结果直接返回
             return predecessorFromAncestor(node.left, key);
         else{
             assert key.compareTo(node.key) > 0;
             // 如果当前节点小于key, 则当前节点有可能是比key小的最大值
-            // 向下搜索结果存储到maxNode中
-            maxNode = predecessorFromAncestor(node.right, key);
-            if(maxNode != null)
-                // maxNode和当前节点node取最大值返回
-                return maxNode.key.compareTo(node.key) > 0 ? maxNode : node;
+            // 向右继续搜索, 将结果存储到tempNode中
+            Node tempNode = predecessorFromAncestor(node.right, key);
+            if(tempNode != null)
+                return tempNode;
             else
-                // 如果maxNode为空, 则当前节点即为结果
+                // 如果tempNode为空, 则当前节点即为结果
                 return node;
         }
     }
@@ -449,21 +447,19 @@ Node successorFromAncestor(Node node, Key key){
         if(node.key.compareTo(key) == 0)
             return null;
 
-        Node minNode;
         if(key.compareTo(node.key) > 0)
             // 如果当前节点小于key, 则当前节点不可能是比key大的最小值
             // 向下搜索到的结果直接返回
             return successorFromAncestor(node.right, key);
         else{
             assert(key.compareTo(node.key) < 0);
             // 如果当前节点大于key, 则当前节点有可能是比key大的最小值
-            // 向下搜索结果存储到minNode中
-            minNode = predecessorFromAncestor(node.left, key);
-            if(minNode != null)
-                // minNode和当前节点node取最小值返回
-                return minNode.key.compareTo(node.key) < 0 ? minNode : node;
+            // 向左继续搜索, 将结果存储到tempNode中
+            Node tempNode = predecessorFromAncestor(node.left, key);
+            if(tempNode != null)
+                return tempNode;
             else
-                // 如果minNode为空, 则当前节点即为结果
+                // 如果tempNode为空, 则当前节点即为结果
                 return node;
         }
     }
