Update bruteforce.cpp

neycyanshi · web-flow · commit ab5d6c46f822 · 2017-02-04T20:44:27.000+08:00
外层while循环中需要判断(left == right)，确定根节点左侧的序列是后序遍历序列。然后将left置为0，right--，重复循环，判断左移后的根节点左侧的序列仍是后序遍历序列。
diff --git a/024-二叉搜索树的后序遍历序列/bruteforce.cpp b/024-二叉搜索树的后序遍历序列/bruteforce.cpp
@@ -19,38 +19,28 @@ using namespace std;
 class Solution
 {
 public:
-    bool VerifySquenceOfBST(vector<int> sequence)
-    {
-        int left = 0, right = sequence.size( ) - 1;
-        while(left < right && right != 0)
-        {
-            //  前一半的元素都小于size
-            while(sequence[left] < sequence[right])
-            {
-                left++;
-            }
-            // 循环结束时, left是第一个大于根的元素的位置
-            //
-            while(sequence[left] > sequence[right])
-            {
-                left++;
-            }
-
-            right--;
-        }
-
-        //  如果循环一直走到right == 0才终止, 说明满足后序遍历的定义
-        if(right == 0)
-        {
-            return true;
-        }
-        else            //  否则说明不满足递归的定义
-        {
-            return false;
-        }
-
-
-    }
+    //下面这种迭代的方法时间复杂度为O(n^2)
+    bool VerifySquenceOfBST_Iteratively(const vector<int>& sequence) {
+		int left = 0, right = sequence.size() - 1;
+		while (left < right && right != 0) {
+			//循环结束时，left是第一个大于根的元素的位置，即右子树首元素下标
+			while (sequence[left] < sequence[right])
+				left++;
+			//循环结束时，left越过右子树末节点，到达根节点
+			while (sequence[left] > sequence[right])
+				left++;
+
+			//如果没有到达根节点，说明不满足左子树所有节点小于根节点，右子树所有节点大于根节点的条件
+			if (left < right)
+				return false;
+			left = 0;
+
+			right--;
+		}
+
+		//如果循环一直到right == 0才终止, 说明以所有节点为根节点，左侧序列均满足后序遍历序列的条件
+		return (right == 0) ? true : false;
+	}
 };
 
 
