// 方法一：递归
var inorderTraversal = function (root) {
  var res = []
  inorder(root, res)
  return res
}

var inorder = function (root, res) {
  if (!root) {
    return
  }
  inorder(root.left, res)
  res.push(root.val)
  inorder(root.right, res)
}

// 方法二：迭代
var inorderTraversal = function (root) {
  var res = [];
  var stack = [];
  while(root || stack.length) {
    while(root) {
      stack.push(root);
      root = root.left;
    }
    root = stack.pop();
    res.push(root.val);
    root = root.right;
  }
  return res;
}

// 方法一：深度优先搜索
var maxDepth = function (root) {
  if (!root) return 0;
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

var maxDepth = function (root) {
  if (!root) return 0;
  var left = maxDepth(root.left);
  var right = maxDepth(root.right);
  return Math.max(left, right) + 1;
}

// 方法二：广度优先搜索
var maxDepth = function (root) {
  if (!root) return 0;
  var res = 0;
  var queue = [root];
  while (queue.length) {
    var temp = [];
    // 遍历当前层的节点
    for (var node of queue) {
      // 将当前节点的左右子节点加入临时数组
      if (node.left) temp.push(node.left);
      if (node.right) temp.push(node.right);
    }
    res += 1;
    queue = temp;
  }
  return res;
}

// 方法一：深度优先搜索（递归）
var invertTree = function (root) {
  if (!root) return null;
  var left = invertTree(root.left);
  var right = invertTree(root.right);
  root.left = right;
  root.right = left;
  return root;
}

// 方法二：广度优先搜索（队列）
var invertTree = function (root) {
  if (!root) return null;
  var deque = [root];
  while (deque.length) {
    var node = deque.pop();
    if (node.left) deque.push(node.left);
    if (node.right) deque.push(node.right);
    // 交换左右子节点
    [node.left, node.right] = [node.right, node.left];
  }
  return root;
}

// 方法一：递归
var isSymmetric = function(root) {
  return !root || check(root.left, root.right);
}

var check = function(p, q) {
  // 左右子节点都是空的，是对称
  if (!p && !q) return true;
  // 只有一边空的，或者值不相同，不是对称
  if (!p || !q || p.val !== q.val) return false;
  return check(p.left, q.right) && check(p.right, q.left);
}

// 方法二：队列
var isSymmetric = function(root) {
  return check(root, root);
}
var check = function(p, q) {
  var queue = [p, q];
  while (queue.length) {
    var n1 = queue.shift();
    var n2 = queue.shift();
    if (!n1 && !n2) continue;
    if (!n1 || !n2 || n1.val !== n2.val) return false;
    queue.push(n1.left, n2.right);
    queue.push(n1.right, n2.left);
  }
  return true;
}

var diameterOfBinaryTree = function (root) {
  var count = 1;
  // 求当前节点为根节点的树，的最大深度
  var depth = function(node) {
    if (!node) return 0;
    var left = depth(node.left);
    var right = depth(node.right);
    // 左子树和右子树的深度加一
    count = Math.max(count, left + right + 1);
    return Math.max(left, right) + 1;
  }
  depth(root);
  return count - 1;
}

var levelOrder = function (root) {
  if (!root) return [];
  var res = [];
  var queue = [root];
  while (queue.length) {
    // 存储下一层节点
    var nextLevel = [];
    // 存储这一层节点
    var curLevel = [];
    for (var node of queue) {
      curLevel.push(node.val);
      if (node.left) nextLevel.push(node.left);
      if (node.right) nextLevel.push(node.right);
    }
    res.push(curLevel);
    queue = nextLevel;
  }
  return res;
}

var sortedArrayToBST = function (nums) {
  return helper(nums, 0, nums.length - 1);
}
var helper = function (nums, left, right) {
  if (left > right) {
    return null;
  }
  var mid = Math.floor((left + right) / 2);
  // 创建根节点
  var root = new TreeNode(nums[mid]);
  // 以根元素左边的升序序列构建左子树
  root.left = helper(nums, left, mid - 1);
  // 以根元素右边的升序序列构建右子树
  root.right = helper(nums, mid + 1, right);
  return root;
}

// 方法一：中序遍历，判断是否升序
var isValidBST = function (root) {
  var arr = [];
  inorder(root, arr);
  for (var i = 1; i < arr.length; i++) {
    if (arr[i] <= arr[i - 1]) {
      return false;
    }
  }
  return true;
}
var inorder = function (root, arr) {
  if (!root) return;
  inorder(root.left, arr);
  arr.push(root.val);
  inorder(root.right, arr);
}

// 方法二：遍历
var isValidBST = function (root) {
  var stack = [];
  var mini = -Infinity;
  while (stack.length || root) {
    while (root) {
      stack.push(root);
      root = root.left;
    }
    root = stack.pop();
    if (root.val <= mini) {
      return false
    }
    mini = root.val;
    root = root.right;
  }
  return true
}

// 方法三：递归
var isValidBST = function(root) {
  return helper(root, -Infinity, Infinity);
};
var helper = function(root, lower, upper) {
  if (!root) return true;
  if (root.val <= lower || root.val >= upper) return false;
  return helper(root.left, lower, root.val) && helper(root.right, root.val, upper);
}

var kthSmallest = function(root, k) {
  var arr = [];
  inorder(root, arr);
  return arr[k - 1];
};
var inorder = function(root, arr) {
  if (!root) return;
  inorder(root.left, arr);
  arr.push(root.val);
  inorder(root.right, arr);
}

// 方法一：层序遍历
var rightSideView = function (root) {
  if (!root) return [];
  var queue = [root];
  var res = [];
  while (queue.length) {
    var cur = [];
    var next = [];
    for (var node of queue) {
      cur.push(node.val);
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
    res.push(cur[cur.length - 1]);
    queue = next;
  }
  return res;
}

// 方法二：递归
var rightSideView = function(root) {
  var res = [];
  var scan = function(node, level) {
    if (!node) return;
    if (res.length <= level) {
      res.push(node.val);
    }
    scan(node.right, level + 1);
    scan(node.left, level + 1);
  }
  scan(root, 0);
  return res;
};

// 方法一：先前序遍历，再连接节点
var flatten = function(root) {
  var arr = [];
  preorder(root, arr);
  for (var i = 0;i < arr.length;i++) {
    arr[i].right = arr[i + 1] || null;
    arr[i].left = null;
  }
};
var preorder = function(root, arr) {
  if (!root) return;
  arr.push(root);
  preorder(root.left, arr);
  preorder(root.right, arr);
}

var buildTree = function(preorder, inorder) {
  var map = new Map();
  // 存储中序遍历节点及对应的索引
  for (var i = 0;i < inorder.length;i++) {
    map.set(inorder[i], i);
  }
  
  var build = function(preLeft, preRight, midLeft, midRight) {
    if (preLeft > preRight) {
      return null;
    }
    // 前序遍历左边界是根节点
    var root = new TreeNode(preorder[preLeft]);
    // 获取根节点在中序遍历数组中的索引
    var midIndex = map.get(preorder[preLeft]);
    // 中序遍历数组，左子树的长度
    var leftLength = midIndex - midLeft;
    // 递归构建左右子树
    // 前序遍历数组中，根节点下一个值就是左子树的左边界，即左子树根节点。左子树右边界的下一个值就是右子树的左边界
    // 中序遍历数组中，根节点左右分别就是左右子树
    root.left = build(preLeft + 1, preLeft + leftLength, midLeft, midIndex - 1);
    root.right = build(preLeft + leftLength + 1, preRight, midIndex + 1, midRight);
    return root;
  }

  return build(0, preorder.length - 1, 0, inorder.length - 1);
};

var pathSum = function(root, targetSum) {
  if (!root) return 0;
  var res = rootSum(root, targetSum);
  res += pathSum(root.left, targetSum);
  res += pathSum(root.right, targetSum);
  return res;
}

var rootSum = function(root, targetSum) {
  if (!root) return 0;
  var res = 0;
  var val = root.val;
  if (val === targetSum) {
    res += 1;
  }
  res += rootSum(root.left, targetSum - val);
  res += rootSum(root.right, targetSum - val);
  return res;
}

var lowestCommonAncestor = function(root, p, q) {
  // 只要当前根节点是p和q中的任意一个，就返回
  if (!root || root === p || root === q) {
    return root;
  }
  // 根节点不是p和q中的任意一个，就继续分别往左子树和右子树找p和q
  var left = lowestCommonAncestor(root.left, p, q);
  var right = lowestCommonAncestor(root.right, p, q);
  // p和q都没找到，那就没有
  if (!left && !right) return null;
  // 左子树没有p也没有q，就返回右子树的结果
  if (!left) return right;
  // 右子树没有p也没有q，就返回左子树的结果
  if (!right) return left;
  // 左右子树都找到p和q了，那就说明p和q分别在左右两个子树上，所以此时的最近公共祖先就是root
  return root;
}

var maxPathSum = function(root) {
  // 最大路径和，初始化为负无穷大，因为节点可以为负数
  var res = -Infinity;
  var depth = function(node) {
    if (!node) return 0;
    // 左、右子树提供的最大路径和
    var left = depth(node.left);
    var right = depth(node.right);
    // 当前子树内部最大路径和，即左右子树最大路径和加上当前节点值
    res = Math.max(res, left + right + node.val);
    // 当前子树对外提供的最大和
    const outputMaxSum = Math.max(left, right) + node.val;
    return Math.max(outputMaxSum, 0);
  }
  depth(root);
  return res;
};

var numIslands = function(grid) {
  var res = 0;
  for (var i = 0;i < grid.length;i++) {
    for (var j = 0;j < grid[0].length;j++) {
      // 注意题目给的是字符串 '1'
      if (grid[i][j] === '1') {
        // 遍历陆地
        area(grid, i, j);
        // 遍历完陆地及其相邻的所有陆地，得到岛屿数+1
        res += 1;
      }
    }
  }
  return res;
};

var area = function(grid, i, j) {
  if (!inArea(grid, i, j)) {
    return;
  }
  if (grid[i][j] !== '1') {
    return;
  }
  // 标记为已遍历
  grid[i][j] = '2';
  // 访问上、下、左、右四个相邻网格点
  area(grid, i - 1, j);
  area(grid, i + 1, j);
  area(grid, i, j - 1);
  area(grid, i, j + 1);
}

var inArea = function(grid, i, j) {
  return i >= 0 && i < grid.length && j >= 0 && j < grid[0].length;
}

var orangesRotting = function(grid) {
  // 新鲜橘子个数
  var fresh = 0;
  // 腐烂橘子的位置
  var badPosition = [];
  for (var i = 0;i < grid.length;i++) {
    for (var j =0;j < grid[0].length;j++) {
      if (grid[i][j] === 1) {
        fresh += 1;
      } else if (grid[i][j] === 2) {
        badPosition.push([i, j]);
      }
    }
  }

  var mins = 0;
  // 当还有新鲜橘子，且还有未遍历的腐烂橘子
  while (fresh && badPosition.length) {
    mins += 1;
    var curBad = badPosition;
    badPosition = [];
    // 遍历已经腐烂橘子位置
    for (var [x, y] of curBad) {
      var nearPosition = [[x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1]];
      // 相邻四个方向的节点
      for (var [i, j] of nearPosition) {
        // 如果在网格内，且有新鲜橘子
        if (i >= 0 && i < grid.length && j >= 0 && j < grid[0].length && grid[i][j] === 1) {
          // 将新鲜橘子腐烂掉
          grid[i][j] = 2;
          // 新鲜橘子数量减一
          fresh -= 1;
          // 记录下腐烂橘子的位置
          badPosition.push([i, j]);
        }
      }
    }
  }
  // 如果跳出循环后还有新鲜橘子，说明这个橘子不会被腐烂掉
  return fresh ? -1 : mins;
};

var canFinish = function(numCourses, prerequisites) {
  // 入度数组
  var inDegree = new Array(numCourses).fill(0);
  var map = new Map();
  for (var i = 0;i < prerequisites.length;i++) {
    var after = prerequisites[i][0];
    var pre = prerequisites[i][1];
    // 求每门课的初始入度
    inDegree[after] += 1;
    // 记录每门课以及依赖于它的后修课
    if (map.has(pre)) {
      map.get(pre).push(after);
    } else {
      map.set(pre, [after]);
    }
  }

  var queue = [];
  // 入度为0的课程入列，说明可以选修了
  for (var i = 0;i < inDegree.length;i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  var count = 0;
  while(queue.length) {
    // 选修一门课
    var cur = queue.shift();
    // 已修课数目+1
    count += 1;
    var afterCourses = map.get(cur);
    // 如果这门课有后修课
    if (afterCourses && afterCourses.length) {
      for (var course of afterCourses) {
        // 后修课的入度减一
        inDegree[course] -= 1;
        // 如果入度减为零，则入列
        if (inDegree[course] === 0) {
          queue.push(course);
        }
      }
    }
  }
  // 选了的课等于总课数，返回true，否则false
  return count === numCourses;
};

var Trie = function() {
  this.arr = [];
  this.map = new Map();
};

/** 
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
  this.arr.push(word);
  this.map.set(word, word);
};

/** 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
  return this.map.get(word) || false;
};

/** 
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function(prefix) {
  return this.arr.find(item => item.startsWith(prefix)) || false;
};

/** 
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */