下面这道题引发了不少思考。越来也越觉得，前中后序遍历 理解 的重要性。

98. 验证二叉搜索树

基本性质，二叉搜索树的中序遍历是升序
最顺的思路就是
1）对 二叉搜索树进行 中序遍历 得到结果 ans
2）判断 ans 是否为升序
优化思路：
在 1）中序遍历过程中，就顺带判断中序遍历的结果

1.标准中序

  1. var isValidBST = function(root) {
  3.     let ans = [];
  4.     function dfs(node) { // 有两种思路理解这段代码：1）递归思路，2）遍历思路
  5.         if (!node) {
  6.             return;
  7.         }
  9.         dfs(node.left);
  10.         ans.push(node.val);
  11.         dfs(node.right);
  12.     }
  14.     dfs(root);
  16.     console.log(ans);
  17. }

判断 数列递增 很简单，这里不写了。

2. 优化

  1. var isValidBST = function(root) {
  2.     let is = true;
  3.     let ans = [];
  4.     function dfs(node) { // 有两种思路理解这段代码：1）递归思路，2）遍历思路
  5.         if (!node) {
  6.             return;
  7.         }
  8.         if (!is) {
  9.             return;
  10.         }
  12.         dfs(node.left);
  13.         if (node.val <= ans[ans.length - 1]) {
  14.             is = false;
  15.             return;
  16.         }
  17.         ans.push(node.val);
  18.         dfs(node.right);
  19.     }
  21.     dfs(root);
  23.     return is;
  24. }

3.去掉数组

  1. var isValidBST = function(root) {
  2.     let is = true;
  3.     // let ans = [];
  4.     let pre = -Infinity;
  5.     function dfs(node) { // 有两种思路理解这段代码：1）递归思路，2）遍历思路
  6.         if (!node) {
  7.             return;
  8.         }
  9.         if (!is) {
  10.             return;
  11.         }
  13.         dfs(node.left);
  14.         if (node.val <= pre) { // 这里决定了pre初始化的值
  15.             is = false;
  16.             return;
  17.         }
  18.         pre = node.val;
  19.         dfs(node.right);
  20.     }
  22.     dfs(root);
  24.     return is;
  25. }