发表于 更新于 分类于

题目描述

验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

  1. 节点的左子树只包含小于当前节点的数。
  2. 节点的右子树只包含大于当前节点的数。
  3. 所有左子树和右子树自身必须也是二叉搜索树。
1
2
3
4
5
输入:
    2
   / \
  1   3
输出: true
1
2
3
4
5
6
7
8
9
输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

代码实现

DFS + Max + Min

https://leetcode.com/problems/validate-binary-search-tree/discuss/158094/Python-or-Min-Max-tm

上面的文章写的很详细了，核心就是要传递一个区间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function (root) {
  function dfs(root, lowerBound = -Infinity, upperBound = Infinity) {
    if (!root) {
      return true;
    }
    if (root.val <= lowerBound || root.val >= upperBound) {
      return false;
    }
    return dfs(root.left, lowerBound, root.val) && dfs(root.right, root.val, upperBound)
  }
  return dfs(root);
};

发表于 更新于 分类于

题目描述

二叉树的中序遍历

给定一个二叉树，返回它的中序遍历。

1
2
3
4
5
6
7
8
输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

代码实现

递归

对于中序遍历，就是 左根右，递归还是很简单的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
  let result = [];
  function recursive(root) {
    if (root) {
      recursive(root.left);
      result.push(root.val);
      recursive(root.right);
    }
  }
  recursive(root);
  return result;
};

栈 + 迭代

如果 root 存在，那么将它放入 stack 中，并且继续指向左子树。

如果 root 不存在，那么取出栈顶元素，将其值放入 res，并将 root 指向右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
  let result = [];
  let stack = [];

  while (stack.length || root) {
    if (root) {
      stack.push(root);
      root = root.left;
    } else {
      let node = stack.pop();
      res.push(node.val);
      root = node.right;
    }
  }
  return result;
};

发表于 更新于 分类于

require : node 和 es6 都支持的引入
export / import : 只有 es6 支持的导出引入
module.exports / exports : 只有 node 支持的导出

CommonJS

Node 里面的模块系统遵循的是 CommonJS 规范。

CommonJS 定义的模块分为: 模块标识 (module)、模块定义 (exports) 、模块引用 (require)。

在一个node执行一个文件时，会给这个文件内生成一个 exports 和 module 对象，而 module 又有一个exports 属性。

它们俩个的关系如下：

1
exports = module.exports = {};

上面的代码等价于：

1
2
module.exports = {...}
exports = module.exports

require 导入的内容是 module.exports 指向的内存块内容，并不是 exports 的。简而言之，区分他们之间的区别就是 exports 只是 module.exports 的引用，辅助后者添加内容用的。

然后呢，为了避免糊涂，尽量都用 module.exports 导出，然后用require导入。

放一段代码：

1
2
3
4
5
6
7
// a.js 中的代码
console.log(module.exports); // {}
console.log(exports);  // {}

exports.x = 200;

exports = {};
1
2
3
4
// b.js 中的代码
let obj = require('./a.js');

console.log(obj); // { x: 200 }

上面的代码相当于：

1
2
3
4
5
6
7
8
9
// 变量 a 相当于 module.exports，变量 b 相当于 exports，最后导出的还是 module.exports
let a = {};
let b = a;
b.x = 200;
console.log(a); // {x: 200}
console.log(b); // {x: 200}
b = {};
console.log(b); // {}
console.log(a); // {x: 200}

ES6模块化

普通导入导出

一个 export 和 多个 export 效果相同，只是写法不同，一个 export 的方式可以看作是简化版。

导入已命名的导出内容必须使用花括号。

多个 export

hello.mjs

1
2
3
4
5
6
const ninja = "a"
export const message = "Hello"

export function sayHiToNinja() {
  return message + " " + ninja
}

index.mjs

1
2
3
4
import { message, sayHiToNinja} from './hello.mjs'

console.log(message) // Hello
console.log(sayHiToNinja()) // Hello a

一个 export

hello.mjs

1
2
3
4
5
6
7
8
const ninja = "a"
const message = "Hello"

function sayHiToNinja() {
  return message + " " + ninja
}

export { message, sayHiToNinja}

index.mjs

1
2
3
4
import { message, sayHiToNinja} from './hello.mjs'

console.log(message) // Hello
console.log(sayHiToNinja()) // Hello a

默认导入导出

通常，我们不需要从模块中导出一组相关的标识符，只需要一个标识符来代表整个模块的导出。

在关键字export后面增加关键字default，指定模块的默认导出。在本例中，模块默认导出类Ninja。虽然指定了模块的默认导出，但是仍然可以导出其他标识符，如导出函数compareNinjas。

hello.mjs

1
2
3
4
5
6
7
8
9
export default class Ninja {
  constructor(name) {
    this.name = name
  }
}

export function compareNinjas(ninja1, ninja2) {
  return ninja1.name === ninja2.name
}

导入默认导出的内容，不需要使用花括号 {}，可以任意指定名称。

index.mjs

1
2
3
4
5
6
7
import ImportedNinja from './hello.mjs'
import { compareNinjas } from './hello.mjs'

const ninja1 = new ImportedNinja("firstName")
const ninja2 = new ImportedNinja("lastName")

console.log(compareNinjas(ninja1, ninja2)) // false

index.mjs 中的 import 语句可以简化成下面：

1
import ImportedNinja, { compareNinjas } from './hello.mjs'

使用重命名

1
export { sayHi as sayHello }
1
import { sayHello } from "./hello.mjs"
1
import { sayHello as greet } from "./hello.mjs"

ES6模块化

导出后修改

一般导出后就不再进行修改，但是如果修改了，那么对于普通导入导出和默认导入导出情况是不同的。

普通

hello.mjs

1
2
3
let awesome = 100;
export { awesome };
awesome = 1;

index.mjs

1
2
import { awesome } from './hello.mjs'
console.log(awesome) // 1

默认

hello.mjs

1
2
3
let awesome = 100;
export default awesome;
awesome = 1;

index.mjs

1
2
import awesome from './hello.mjs'
console.log(awesome) // 100