剑指第二版/剑指Offer33.二叉搜索树的后序遍历序列.html

<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>剑指 Offer 33. 二叉搜索树的后序遍历序列</title>
  </head>
  <body>
    <script>
      // https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/

      // 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
      // 参考以下这颗二叉搜索树：
      // 提示：
      // 数组长度 <= 1000

      /**
       * @param {number[]} postorder
       * @return {boolean}
       */
      var verifyPostorder = function (postorder) {};

      // --- answer-1 ---

      // 二叉搜索树 左<根<右
      // 后序遍历 左右跟
      // 最后一个根节点
      // 前面分成两部分，一部分都小于根节点，另一部分都大于根节点
      var verifyPostorder = function (postorder) {
        function verify(start, end) {
          if (start >= end) return true;
          let i = start;
          // 小于根节点的部分
          while (postorder[i] < postorder[end]) i++;
          let mid = i;
          // 大于根节点的部分
          while (postorder[i] > postorder[end]) i++;
          // 子树
          return i === end && verify(start, mid - 1) && verify(mid, end - 1);
        }
        return verify(0, postorder.length - 1);
      };

      // --- answer-1 ---

      // --- answer-2 ---

      // 遍历
      // 后序遍历的倒序为 根右左 根 < 右 右 > 左
      var verifyPostorder = function (postorder) {
        let stack = [];
        let root = Number.MAX_VALUE;
        for (let i = postorder.length - 1; i >= 0; i--) {
          if (postorder[i] > root) return false;
          while (stack.length && stack[stack.length - 1] > postorder[i])
            root = stack.pop();
          stack.push(postorder[i]); // 大的部分
        }
        return true;
      };

      // --- answer-2 ---

      //      5
      //     / \
      //    2   6
      //   / \
      //  1   3

      var postorder = [1, 6, 3, 2, 5];
      var result = false;

      var postorder = [1, 3, 2, 6, 5];
      var result = true;

      var postorder = [1, 3, 2, 5];
      var result = true;

      var postorder = [1, 2, 5, 10, 6, 9, 4, 3];
      var result = false;

      var postorder = [4, 8, 6, 12, 16, 14, 10];
      var result = true;

      var postorder = [1, 2, 3, 4, 5];
      var result = true;

      var postorder = [5, 2, -17, -11, 25, 76, 62, 98, 92, 61];
      var result = false;

      console.log("postorder = ", postorder);
      console.log("result = ", result);
      console.log("verifyPostorder = ", verifyPostorder(postorder));
    </script>
  </body>
</html>