Same tree

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

1
2
3
4
5
6
7

Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true

Example 2:

1
2
3
4
5
6
7

Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]

Output: false

Example 3:

1
2
3
4
5
6
7

Input:     1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

Output: false

题意分析

检查给定两个二叉树是否为结构相同且对应值相等的相同二叉树。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    if(p == null && q == null) return true;
    if(p == null || q == null) return false;
    if(p.val == q.val) {
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
    return false;
};

Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Input: [1,3,null,null,2]

   1
  /
 3
  \
   2

Output: [3,1,null,null,2]

   3
  /
 1
  \
   2

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Input: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

Output: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

Follow up:

• A solution using O(n) space is pretty straight forward.
• Could you devise a constant space solution?

题意分析

给定一个二叉搜索树，其中两个节点的位置被错误放置。让我们找到这两个节点并将其交换使之成为一个合法的二叉搜索树。分析可知，二叉搜索树的中序遍历应该是递增序的，我们将给定输入的树进行中序遍历，有两种可能存在的情况：其一是两个错误的元素紧邻放置，那么中序遍历的结果中只有这两个错误的邻居元素是逆序的；其二是两个错误的元素不相邻，那么中序遍历结果中会存在两个逆序。如3 25 7 8 10 15 20 5，其中的25和5，这两个需要做交换使之成为3 5 7 8 10 15 20 25。其中25和5是应当做交换的非紧邻元素，那么我们可以发现25大于7，20大于5这两对逆序，并取第一个逆序的第一个元素和第二个逆序的第二个元素做交换。而在3 5 8 7 10 15 20 25这一个紧邻元素需要做交换的例子中，我们并不存在第二个逆序对，所以只需要找到唯一的逆序对，将其做交换即可。

代码实现

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
// first指向第一个逆序对的第一个元素，middle指向第一个逆序对的第二个元素，last指向第二个逆序对的第二个元素
var first, middle, last, prev;
var recoverTree = function(root) {
    first = middle = last = prev = null;
    correct(root);
    
    // last存在代表有两个逆序对，这时候middle也是存在的，需要严格按照这个顺序
    if(first != null && last != null) {
        let temp = first.val;
        first.val = last.val;
        last.val = temp;
    } else if(first != null && middle != null) {
        let temp = first.val;
        first.val = middle.val;
        middle.val = temp;
    }
};

function correct(root) {
    if(root != null) {
        correct(root.left);
        
        if(prev != null && prev.val > root.val) {
            if(first == null) {
                first = prev;
                middle = root;
            } else {
                last = root;
            }
        }
        prev = root;
        correct(root.right);
    }
}

Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.

Example:

1
2
3
4
5
6

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]
Follow up: Recursive solution is trivial, could you do it iteratively?

题意分析

实现中序遍历二叉树。最简单是递归版本，然后设计一个迭代版本。迭代版本中我们设置一个栈，用来存放我们看到过的结点，当到达树最左侧结点时，就将当前结点出栈，并检查最左侧结点是否存在右子树，如果有我们需要以同样的方法迭代右子树。

代码实现

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
28

/**
 * 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) {
    var res = [];
    helper(root, res);
    return res;
};

function helper(root, res) {
    if(root !== null) {
        if(root.left !== null) {
            helper(root.left, res);
        }
        res.push(root.val);
        if(root.right !== null) {
            helper(root.right, res);
        }
    }
}

递推方程是T(n) = 2 * T(n / 2) + 1，时间复杂度为O(n)。空间复杂度最坏情况为O(n)，当树向一侧倾斜时出现。而平均情况下，空间复杂度为O(log(n))。

迭代版本

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

/**
 * 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) {
    var stack = [];
    var res = [];
    var curr = root;
    while(curr !== null || stack.length !== 0) {
        while(curr !== null) {
            stack.push(curr)
            curr = curr.left;
        }
        curr = stack.pop();
        res.push(curr.val);
        curr = curr.right;
    }
    return res;
};

因为要遍历到所有节点，时间复杂度为O(n)，额外用了一个栈，空间复杂度为O(n)。

第三种方案是利用线索二叉树。

• 用root初始化current
• while current不空：
  • 如果current没有左子树，push进current的值，然后current指向右子树
  • 否则有左子树，找到current左子树的最右侧节点，将current作为这个节点的右子树。

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
28
29

/**
 * 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) {
    var curr = root;
    var res = [];
    while(curr !== null) {
        if(curr.left === null) {
            res.push(curr.val);
            curr = curr.right;
        } else {
            var pre = curr.left;           
            while(pre.right !== null) pre = pre.right;
            var temp = curr;
            pre.right = curr;
            curr = temp.left;
            temp.left = null;
        }
    }
    return res;
};

时间复杂度和空间复杂度都为O(n)。

该方法的策略就是用中序遍历的次序重新构建一个线索树。

层叠，特殊性和继承

层叠

在各样式声明冲突时，层叠性考虑这些去解析：

• 样式表来源
• 选择器的特殊性
• 源顺序

样式表来源

UA样式

开发人员添加的样式表并不是唯一被浏览器应用的样式表，此外，用户代理(User Agent)也有自己的一套规则，它们和author styles一并用于样式渲染。有些浏览器还让用户自定义样式，暂不考虑。

UA的样式因浏览器不同而不同，但大体保持如下：h1到h6以及p具有上下外边距，列表（ol和ul）具有左内边距，上下外边距，而链接颜色和字体大小也被设定。列表的list-style-type设置为disc显示为无序列表的左侧圆点。

UA样式可被author style重写，因为后者优先级更高。如果在html中引入多个样式表，它们都具有author style的优先级别。

important声明

声明的分号前加一个!important会以更高的优先级源来处理。所以author important>author>user agent。

每个元素的property都被独立处理，当在p标签上设置粗体时，并不会影响p标签的UA定义的上下外边距样式。

特殊性

如果矛盾声明无法通过源来解决，那么就需要考虑声明的特殊性。浏览器用两部分来评估特殊性，一方面是HTML应用的行内样式，一方面是用选择器应用的样式。

行内样式

行内样式直接应用到定位元素，因为他们不存在选择器一说。而应用的行内样式会覆盖style标签或者外部样式表定义的样式。

为了在外部样式表或者style标签中重写行内样式声明，可以添加!important声明使之成为具有更高优先级的源。如果行内样式添加了!important，那么它的声明永远不会被覆盖，最好在样式表中使用!important。

选择器特殊性

简言之，选择器的特殊性这样理解：

• 如果一个选择器有更多的ID选择器，则优先级更高
• 如果ID选择器相同，则具有更多的类选择器的优先级更高
• 如果类选择器也相同，则看元素选择器

伪类选择器(:hover)和属性选择器([type=”input”])和类选择器特殊性等同，而通用选择器(*)和连接符(> + ~)对特殊性没有影响。

如果有时候你写的规则无效，很有可能是别的具有更高特殊性的规则重写了它。许多程序员滥用id选择器却不知道id选择器具有更高的特殊性，使得后期重写其样式变得困难，因为你必须使用另一个id选择器。

特殊性记法

普遍的记录特殊性的方法就是用逗号分割的3个数字，依次代表id选择器，类选择器和元素选择器的数量。1，0，0的特殊性要高于0，10，1，因为id选择器具有更高优先级。

有时，人们也使用4个数字的记法，其中第一个数字代表行内样式，0代表没有行内样式，1代表有行内样式，存在行内样式时，无论后面数字是多少，都会解析为行内样式。

特殊性注意事项

尽可能降低使用的选择器的特殊性，便于后期维护。

理解源顺序

如果源和特殊性都相同，就要看源顺序，出现在同一样式表中靠后的规则被应用，出现在同一页面后引入的样式表样式被应用。

1
2
3
4
5
6
7
8
9
10
11
12
13

a:link {
color: blue;
text-decoration: none;
}
a:visited {
color: purple;
}
a:hover {
text-decoration: underline;
}
a:active {
color: red;
}

同样的特殊性，定义在后面的样式被应用，当我们hover的时候，样式要覆盖掉link状态的样式和visited状态的样式，而active状态下要覆盖掉hover状态的样式。可通过LoVe/HAte来助记。

层叠值（cascaded value）

浏览器遵循这三个步骤——源，特殊性，源顺序为页面每个元素的每个属性做解析，并最终得到一个层叠值做渲染。每个属性只可能有一个层叠值，如果一个属性从始至终没有被任何源指定，那么它没有层叠值。比如p元素可能没有内边距或者边框。

两个经验法则

• 不要使用ID选择器
• 不要使用!important

不过也有例外的情况，只是不要将它们作为赢得特异性战争的武器而已。

继承

如果属性没有层叠值，那么它可能会从祖先元素继承。如在body上定义font-family，那么所有的后代元素都会自动继承这个规则。

并非所有属性都会被继承，这些被继承的属性多是你期望要被继承的属性，一般和文字相关：color , font , font-family , font-size , font-weight , font-variant , font-style , line-height , letter-spacing , text-align , text-indent , text-transform , white-space , word-spacing等。

还有列表相关的list-style , list-style
-type , list-style-position , list-style-image等。表格边框属性border-collapse , border-spacing也被继承。

特殊值

有两个特殊值可被用于设置属性来修改你的层叠：inherit和initial。

处理事件

一些程序和直接的用户输入打交道，如鼠标和键盘行为。那种类型的输入不能作为一个组织良好的数据结构获得——它实时的一块接一块的到来，并且程序被期望随时响应。

事件处理器

想象一个接口，其中唯一的检测是否键盘上某一按键被按下的方式就是读取那个键的当前状态。为了能够响应按键，你必须持续读取那个键的状态，如此一来你就能在它释放之前捕捉到它。执行其他时间密集型的计算是危险的因为你可能错过按键。

一些基本的机器确实像这样处理输入。从这一步开始，硬件或者操作系统注意到按键操作并将其放到一个队列。程序就可以为新事件周期性检查队列并对发现的事情作出反应。

当然，它必须记住查看队列，并且经常这样做，因为在按键被按下和程序注意到事件之间的任何时间，都将导致软件感觉没有响应。这种方法叫做轮询。大多数的开发人员倾向于避免它。

一个更好的机制就是当事件发生的时候，系统主动通知我们的代码。浏览器通过允许我们将函数注册为特定事件的处理器来实现这个。

1
2
3
4
5
6

<p>Click this document to activate the handler.</p>
<script>
  window.addEventListener("click", () => {
    console.log("You knocked?");
  });
</script>

window绑定指的是浏览器提供的内建对象。它代表了包含文档的浏览器窗口。调用它的addEventListener方法使得第一个参数事件发生的时候，第二个参数被调用。

事件和DOM节点

每个浏览器事件处理器都在上下文中注册。在前面的例子中，我们在window对象上调用addEventListener来为整个窗口注册一个处理器。这样的方法也能在DOM元素和其它类型的对象上发现。事件监听器只在事件发生在所注册对象的上下文中发生时才会调用。

1
2
3
4
5
6
7
8

<button>Click me</button>
<p>No handler here.</p>
<script>
  let button = document.querySelector("button");
  button.addEventListener("click", () => {
    console.log("Button clicked.");
  });
</script>

文档对象模型

当你在浏览器中打开一个网页的时候，浏览器获取到页面的HTML文本并解析它，非常像我们12章的解析器。浏览器构建一个文档结构的模型，并使用这个模型在屏幕上绘画页面。

这个文档的表示就是JS在它的沙箱里可以获得的玩具之一。它是一个你可以读取或者修改的数据结构。它表现得像一个动态的数据结构：当被修改的时候看，屏幕上的页面就会更新来反映这种变化。

文档结构

你可以把HTML文档想象为一个嵌套的盒子集合。像<body></body>包围其他的标签，这些被包围的标签返回来又包含其他标签或者文本。这有一个例子：

1
2
3
4
5
6
7
8
9
10
11
12

<!doctype html>
<html>
  <head>
    <title>My home page</title>
  </head>
  <body>
    <h1>My home page</h1>
    <p>Hello, I am Marijn and this is my home page.</p>
    <p>I also wrote a book! Read it
      <a href="http://eloquentjavascript.net">here</a>.</p>
  </body>
</html>

页面有如下结构

浏览器用于表示文档的数据结构遵循这种形状。对于每个盒子，有一个我们可以交互的对象，我们可以发现它代表的HTML标签以及包含的盒子和文本。这种表示叫做文档对象模型，或者简言之DOM。

全局绑定document赋予我们获取这些对象的能力。documentElement属性指的是表示<html>标签的对象。因为每个HTML文档有一个head和一个body，它也有head和body属性，指向那些元素。

树

回想一下12章的语法树。他们的结构非常类似浏览器文档的结构。每一个节点可能引用其他的儿子节点，反过来也可能有它们的儿子节点。这种形状在嵌套的结构中很典型，元素可以包含类似于它们自己的子元素。

我们将这样的数据结构叫做树，当他有一个分支结构时，没有环路（一个节点不能包含自己，直接或间接都不行），并且有一个单一的定义良好的根。在DOM中，document.documentElement作为根元素存在。

在计算机科学中树经常出现。除了表示如HTML文档或者程序这样的递归结构，他们经常被用于维护有序的数据集，因为元素相比在普通数组中，可以更高效的查找或者插入。

一个典型的树有不同种类的节点。egg语言的语法树有标识符，值和应用节点（application node）。应用节点可能包含儿子，而标识符和值是叶子节点，或者说是不包含儿子的节点。

DOM的元素节点也是一样，它们代表HTML标签，决定了文档的结构。这些可以有儿子节点。这样的节点的一个例子就是document.body。这些儿子节点中的一些可能是叶子节点，如文本或者注释节点。

每一个DOM节点对象拥有一个nodeType属性，包含一个数字代码标识节点类型。元素的代码为1，也定义在常量属性Node.ELEMENT_NODE中。文本节点，代表文档中的一部分文本，代码为3（Node.TEXT_NODE）。注释代码为8（Node.COMMENT_NODE）。

另一种可视化我们文档树的方式如下：

文本节点作为叶子节点，箭头用来表明节点间的父子关系。

标准

使用神秘的数字代码标识节点类型不是像JS做的事情。本章的稍后将会看到DOM接口的其他部分同样笨重并且陌生。原因就是DOM接口不仅是为JS设计的。相反，它尽力成为一个语言中立的接口来使得自己也可以被用到其它系统——不仅是HTML也包括XML，XML是一种有着类HTML语法的通用数据格式。

这是不幸的。标准通常是有用的。但是这种情况下，优势（跨语言一致性）并不是那么引人注目的。有一个和所使用的语言恰当集成的接口要省不少时间，比起跨语言使用熟悉的接口。

作为这种不好集成的一个例子，考虑dom中元素节点的childNodes属性。这个属性保存了一个类数组的对象，有一个length属性和一些以数字为标签的属性用来获取子节点。但是它是NodeList类型的一个实例，并不是一个真正的数组，所以没有slice和map方法。

还有一些问题仅仅是糟糕的设计。例如，没有办法创建一个新节点并立刻向上面添加儿子节点或者属性。相反，你必须首先创建它，并且使用副作用一个接一个添加儿子和属性。与DOM交互的代码很长，重复并且丑陋。

但是这些缺陷并不致命。因为JS允许我们创造自己的抽象，设计改进的方式来表达你执行的操作是可能的。浏览器编程的许多库都带有这些工具。

遍历树

DOM节点包含许多到其他临近节点的链接。如图：

即使图只展示了每种类型的一个链接，每个节点都有一个parentNode属性指向它的父节点（如果有的话）。类似的，每个元素节点（节点类型1）有一个childNodes属性指向一个保存它儿子节点的类数组对象。

理论上，你可以使用这些父子链接来在树中做任何移动。但是JS也给你获取一些额外的方便的链接。firstChild和lastChild属性指向第一个和最后一个子元素或者对于没有孩子的节点值为null。相似地，previousSibling和nextSibling指向邻近的节点，就是同一个父节点下的立刻出现在他们之前的节点和它们之后的节点。对于第一个儿子，previousSibling将会为null，而对于最后一个儿子，nextSibling为null。

还有一个children属性，类似于childNodes属性但是只包含元素（类型1）儿子，没有其他类型的儿子节点。当你对文本节点不感兴趣时这是有用的。

当处理类似这个的嵌套数据结构时，递归函数通常很有用。下面的函数扫描一个文档的包含给定字符串的文本节点并且当发现的时候返回true。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

function talksAbout(node, string) {
    if(node.nodeType == Node.ELEMETN_NODE) {
        for(let i = 0; i < node.childNodes.length; i++) {
            if(talksAbout(node.childNodes[i], string)) {
                return true;
            }
        }
        return false;
    } else if (node.nodeType == Node.TEXT_NODE) {
        return node.nodeValue.indexOf(string) > -1;
    }
}

console.log(talksAbout(document.body, "book"));
// -> true

因为childNodes不是一个真正的数组，我们不能用for/of遍历，并且必须使用常规的for循环或者使用Array.from。

文本节点的nodeValue属性保存了它表示的文本字符串。

发现元素

在这些父子兄弟之间导航这些链接很有用。但是如果我们想要在一个文档中找到特定的节点，通过在document.body开始并且遵循一个固定的路径是错误的主意。这样做会对我们的文档结构做出假设——随后还可能会改变结构。另一个复杂的因素是即使对于节点间的空白文本节点也会创建。例子中的document的<body>标签不仅只有三个孩子（<h1>和两个<p>），实际上有七个节点：这三个，加上前后的空白以及中间的空白。

所以如果我们想要在文档中获取链接的href属性，我们不想要说类似”获取document body第六个孩子的第二个孩子”这样的话语。如果我们说“获取document中的第一个链接”更好。我们当然可以这样做。

1
2

let link = document.body.getElementsByTagName("a")[0];
console.log(link.href);

所有的元素节点有一个getElementsByTagName方法，收集所有给定标签名字的元素，直接或者间接eider那个节点的孩子并且将其作为一个类数组对象返回。

为了找到一个特定的单个节点，你可以给它一个id属性并且使用document.getElementById来代替。

1
2
3
4
5
6
7

<p>My ostrich Gertrude:</p>
<p><img id="gertrude" src="img/ostrich.png"></p>

<script>
  let ostrich = document.getElementById("gertrude");
  console.log(ostrich.src);
</script>

第三种相似的方法是getElementsByClassName，类似于getElementsByTagName，搜索元素节点的内容，并且检索所有在他们class属性中包含给定字符串的元素。

改变document

几乎所有的关于DOM数据结构的东西可以被改变。通过改变父子关系文档树的形状可以被改变。节点有一个remove方法来从他们当前的父节点中移除它们。为了向一个元素节点添加一个子节点，我们可以使用appendChild，将子节点添加在孩子节点列表的末尾，或者insertBefore，将第一个参数节点插入到第二个参数节点之前。

1
2
3
4
5
6
7
8

<p>One</p>
<p>Two</p>
<p>Three</p>

<script>
  let paragraphs = document.body.getElementsByTagName("p");
  document.body.insertBefore(paragraphs[2], paragraphs[0]);
</script>

一个节点只能在文档中占据一个位置。因此，将段落3插入到段落一前面将首先从文档末尾移除它并且然后在前面插入它，导致312的顺序。所有插入结点的操作，作为一种副作用都会导致它被从当前位置移除（如果有的话）。

replaceChild方法被用于用另一个节点替换一个孩子节点。接受一个新节点参数和另一个要被替换的节点。被替换的节点必须是方法调用的对象的孩子。注意replaceChild和insertBefore期望新节点是它们的第一个参数。

创造节点

假如我们想要书写一个script，来将document中所有图片标签替换成其alt属性中的文字。

这不仅涉及到移除图片，同时还要添加一个新的文本节点来替换他们。文本节点使用document.createTextNode方法创建。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

<p>The <img src="img/cat.png" alt="Cat"> in the
  <img src="img/hat.png" alt="Hat">.</p>

<p><button onclick="replaceImages()">Replace</button></p>

<script>
  function replaceImages() {
    let images = document.body.getElementsByTagName("img");
    for (let i = images.length - 1; i >= 0; i--) {
      let image = images[i];
      if (image.alt) {
        let text = document.createTextNode(image.alt);
        image.parentNode.replaceChild(text, image);
      }
    }
  }
</script>

给定一个字符串，createTextNode创造一个我们可以用于插入文档的文本节点并且让他展示在屏幕上。

循环开始于列表末尾的图片。这是必须的，因为由方法类似getElementsByTagName（或是一个类似childNodes的属性）返回的节点列表是实时变化的。也就是随着文档变化而变化。如果我们从前面开始，移除第一个图片将会导致列表失去它的第一个元素，所以第二次循环重复的时候，i为1，循环将会停止，因为集合的长度也为1了。

如果你想要一个可靠的节点集合，对应于一个实时变化的，你可以通过调用Array.from来转换集合到一个真正的数组。

1
2
3
4

let arrayish = {0: "one", 1: "two", length: 2};
let array = Array.from(arrayish);
console.log(array.map(s => s.toUpperCase()));
// → ["ONE", "TWO"]

为了创建元素节点，你可以使用document.createElement方法。这个方法接受一个标签名称并且返回一个给定类型的新的空节点。

下面的例子定义了一个实用函数elt，创造一个元素节点，并且将剩下的参数看作是该节点的孩子节点。函数然后被用于向一个引言添加来源。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

<blockquote id="quote">
  No book can ever be finished. While working on it we learn
  just enough to find it immature the moment we turn away
  from it.
</blockquote>

<script>
  function elt(type, ...children) {
    let node = document.createElement(type);
    for (let child of children) {
      if (typeof child != "string") node.appendChild(child);
      else node.appendChild(document.createTextNode(child));
    }
    return node;
  }

  document.getElementById("quote").appendChild(
    elt("footer", "—",
        elt("strong", "Karl Popper"),
        ", preface to the second editon of ",
        elt("em", "The Open Society and Its Enemies"),
        ", 1950"));
</script>

属性

一些元素属性，比如链接的href属性，可以通过元素的DOM对象的同名属性获取。这是最常用的标准属性的情况。

但是HTML允许你设置任何你想要在节点上的属性。因为它允许我们在文档中存储额外的信息这是很有用的。如果你捏造自己的属性名，即便这样的属性不会在元素的节点上作为属性呈现。你必须使用getAttribute和setAttribute方法来和他们交互。

1
2
3
4
5
6
7
8
9
10
11

<p data-classified="secret">The launch code is 00000000.</p>
<p data-classified="unclassified">I have two feet.</p>

<script>
  let paras = document.body.getElementsByTagName("p");
  for (let para of Array.from(paras)) {
    if (para.getAttribute("data-classified") == "secret") {
      para.remove();
    }
  }
</script>

推荐在这样捏造的属性前面加上data-前缀来确保他们不和其他任何属性冲突。

有一个常用的属性class，是JS语言的一个关键字。由于历史原因——一些古老的JS实现不能够处理匹配关键字的属性名——用于获取这个attribute的property因此被叫做className。你也可以用它的真名获取class，通过使用getAttribute和setAttribute方法。

布局

你可能已经注意到了不同类型的元素以不同的方式布局。一些类似于p标签和标题标签的元素，占据文档的全部宽度，并且在独立的行上渲染。这些被叫做块级元素。而类似a标签和strong标签，和它们周围的文本在同一行上渲染。这样的元素叫做行内元素。

对于任何给定的文档，浏览器能够计算一个布局，基于每个元素的类型和内容给出大小和位置。这个布局然后就被用于绘画文档。

元素的大小和位置可以通过JS获取。offsetWidth和offsetHeight属性告诉你元素占据的像素空间。一个像素是浏览器中的度量的最基本单位。它传统上对应于屏幕可以绘画的最小的点，但是在现代浏览器上可以画非常小的点，可能就不是这样了，一个浏览器像素可能跨越多个显示点。

相似地，clientWidth和clientHeight给出元素内部的空间大小，忽略边框宽度。

1
2
3
4
5
6
7
8
9

<p style="border: 3px solid red">
  I'm boxed in
</p>

<script>
  let para = document.body.getElementsByTagName("p")[0];
  console.log("clientHeight:", para.clientHeight);
  console.log("offsetHeight:", para.offsetHeight);
</script>

找到在屏幕上的元素最准确位置的最高效的方式是getBoundingClientRect方法。它返回一个具有top,bottom,left和right属性的对象，表明元素边缘相对于屏幕左上角的像素位置。如果想要他们相对于整个文档，你必须要添加当前的滚动位置，你可以在pageXOffset和pageYOffset绑定中找到。

为一个文档布局是一项繁重的工作。考虑到速度，每当你改变文档的时候，浏览器引擎会尽可能长地等待，而不会立刻重新布局。当一个改变文档的JS程序运行结束的时候，浏览器就必须计算一个新的布局来将改变的文档绘画到屏幕上。当程序通过读取类似offsetHeight或者调用getBoundClientRect这样的属性来获取某个东西的位置或者大小时，提供正确的信息也需要计算一个布局。

一个反复读取DOM布局信息和改变DOM的程序会强制执行大量的布局计算，并且将因此运行的非常慢。下面的代码是一个这样的例子。它包含两个不同的程序，它构建一行2000像素宽的X字符并且测量每次花费的时间。

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

<p><span id="one"></span></p>
<p><span id="two"></span></p>

<script>
  function time(name, action) {
    let start = Date.now(); // Current time in milliseconds
    action();
    console.log(name, "took", Date.now() - start, "ms");
  }

  time("naive", () => {
    let target = document.getElementById("one");
    while (target.offsetWidth < 2000) {
      target.appendChild(document.createTextNode("X"));
    }
  });
  // → naive took 32 ms

  time("clever", function() {
    let target = document.getElementById("two");
    target.appendChild(document.createTextNode("XXXXX"));
    let total = Math.ceil(2000 / (target.offsetWidth / 5));
    target.firstChild.nodeValue = "X".repeat(total);
  });
  // → clever took 1 ms
</script>

样式

我们已经看见了不同的HTML元素可以以不同的方式绘画。一些作为块级元素显示，而另一些作为行内元素。一些添加样式，如strong使得成为粗体，a标签使得颜色变蓝并且添加下划线。

img标签展示图片的方式或者a标签在单击时做链接跳转和元素类型有关。但是我们可以改变关联到一个元素的样式，如文字颜色或者下划线。这是一个使用style属性的例子：

1
2

<p><a href=".">Normal link</a></p>
<p><a href="." style="color: green">Green link</a></p>

一个style属性可以包含一个或者多个声明，声明激素hi属性加上一个冒号和一个值。当有超过一个声明时，他们必须以分号分离。color: red; border: none。

文档的许多方面都可以被样式影响。例如，display属性控制元素以块级元素还是行内元素显示。

1
2
3

This text is displayed <strong>inline</strong>,
<strong style="display: block">as a block</strong>, and
<strong style="display: none">not at all</strong>.

block标识使得它们自己独在一行因为块级元素不和它们周围的文本显示在一起。最后一句话没有显示，因为display:none使得元素不在屏幕上显示。这是一种隐藏元素的新方式。相比于完全从文档中移除它们隐藏起来更好因为使得随后重新显示它们更加容易。

JS代码可以通过元素的style属性直接修改元素的样式。这个属性保存了一个包含所有可能的样式属性的对象。这些属性值是字符串，为了改变元素的某个样式我们可以写这些属性。

1
2
3
4
5
6
7
8
9

<p id="para" style="color: purple">
  Nice text
</p>

<script>
  let para = document.getElementById("para");
  console.log(para.style.color);
  para.style.color = "magenta";
</script>

一些样式属性名字包含短横线，如font-family。因为这样的属性名在JS中看上去比较笨拙，style对象中的这样的属性名就移除了短横线，并且在他们后面的单词首字母大写（style.fontFamily）。

层叠样式

HTML的样式系统叫做CSS，也就是层叠样式表。一个样式表就是在文档中给元素添加样式的一套规则。可以在<style>标签中给出。

1
2
3
4
5
6
7

<style>
  strong {
    font-style: italic;
    color: gray;
  }
</style>
<p>Now <strong>strong text</strong> is italic and gray.</p>

名字中的层叠指出多个这样的规则被组合去产生元素最终的样式。例子中，默认的<strong>标签的样式，也就是font-weight: bold，被在<style>标签中的样式重写了，添加了font-style和color。

当多个规则应用到同一属性时，最近的读取规则获得一个高优先级并得到应用。所以如果<style>标签中包含font-weight: normal与默认的font-weight规则矛盾，文本就将会是normal，而不是bold的。直接应用到节点的style属性中的样式有最高的优先级并且总是胜出。

可以不用标签名在CSS规则中定位。.abc应用到所有类属性中包含”abc”的元素。#xyx应用到所有id属性包含”xyz”的元素（应该是文档中独一无二的）。

1
2
3
4
5
6
7
8
9
10
11
12

.subtle {
  color: gray;
  font-size: 80%;
}
#header {
  background: blue;
  color: white;
}
/* p elements with id main and with classes a and b */
p#main.a.b {
  margin-bottom: 20px;
}

优先规则只有在规则有相同的特殊性时才具有就近原则。一个规则的特殊性就是能够多精准的描述匹配元素。例如，定位p.a要比定位p或者.a要精准，并且会有更高的优先级。

p > a{...}标记应用给定样式到所有是p标签直接孩子的a标签元素。相似地，p a{..}应用到p标签内的a标签，不管他们是不是直接孩子，抑或是间接孩子。

查询选择器

我们不会在这本书中使用太多样式表。在浏览器中编程理解他们是有帮助的，但是它们很复杂，要单独写一本书。

我介绍选择器语法的主要原因——用在样式表中决定一组样式应用到哪些元素上——是我们可以使用这种微语言作为一种高效的方式去查找DOM元素。

querySelectorAll方法，同时定义在document对象和元素节点，接受一个选择器字符串并返回一个包含所有匹配元素的NodeList。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

<p>And if you go chasing
  <span class="animal">rabbits</span></p>
<p>And you know you're going to fall</p>
<p>Tell 'em a <span class="character">hookah smoking
  <span class="animal">caterpillar</span></span></p>
<p>Has given you the call</p>

<script>
  function count(selector) {
    return document.querySelectorAll(selector).length;
  }
  console.log(count("p"));           // All <p> elements
  // → 4
  console.log(count(".animal"));     // Class animal
  // → 2
  console.log(count("p .animal"));   // Animal inside of <p>
  // → 2
  console.log(count("p > .animal")); // Direct child of <p>
  // → 1
</script>

不像如getElementsByTagName这样的方法，由querySelectorAll返回的对象不是实时的。当你改变文档的时候他不会改变。他也不是一个真正的数组，也可以使用Array.from将其转换为一个数组。

querySelector方法（没有all部分）以一种相似的方式工作。将只返回第一个匹配的元素，或者没有匹配元素时返回null。

定位和动画

position样式属性以一种强大的方式影响布局。默认属性值为static，意味着元素坐落在文档中的正常位置。当被设置为relative时，元素仍然在文档中占据空间，但是现在top和left样式属性可被用于相对于正常的位置移动他。当position被设置为absolute时，元素被从正常的文档流中移除——那就是说，他不在占据空间并且可能被其他元素覆盖。同时，它的top和left属性可用于相对最近的position属性不是static的外部元素的左上角来绝对定位，或者如果没有这样的元素时，相对文档来定位。

我们可以利用这个来创造动画。下面的文档显示了一个猫的图片，以椭圆轨迹来回移动。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

<p style="text-align: center">
  <img src="img/cat.png" style="position: relative">
</p>
<script>
  let cat = document.querySelector("img");
  let angle = Math.PI / 2;
  function animate(time, lastTime) {
    if (lastTime != null) {
      angle += (time - lastTime) * 0.001;
    }
    cat.style.top = (Math.sin(angle) * 20) + "px";
    cat.style.left = (Math.cos(angle) * 200) + "px";
    requestAnimationFrame(newTime => animate(newTime, time));
  }
  requestAnimationFrame(animate);
</script>

我们的图片在页面居中并且position为relative。我们将重复改变图片的top和left样式来移动它。

该script使用requestAnimationFrame，每当浏览器准备重绘屏幕的时候调度animate函数去运行。animate函数本身再次调用requestAnimationFrame来调度下次升级。当浏览器窗口（或标签页）激活的时候，这将导致变化以每秒60帧做升级，这将产生一个好看的动画。

如果我们只是在循环中改变DOM，页面将会冻结，并且什么也不会展示在屏幕上。当JS程序运行的时候浏览器不会改变它们的显示，它们也不允许和页面产生任何交互。这就是为什么我们需要requestAnimationFrame——它让浏览器知道我们现在做完了，他可以继续做浏览器做的事情，如升级画面，响应用户行为。

当前时间作为一个参数传进动画函数。为了确保猫每毫秒的稳定运动，它基于当前时间和上次函数运行的时间差确定角度变化的速度。如果仅仅是每一步移动一个固定的角度，如果在同一台计算机上运行的另一个繁重任务是阻止函数运行几分之一秒，那么这个函数就会断断续续。

以圆移动通过三角函数Math.cos和Math.sin实现的。对于那些不熟悉他们的人，我将简要介绍他们，因为我们偶尔会在这本书中用到。

Math.cos和Math.sin对于找到半径为1的圆心在0，0的圆上的点是有用的。这两个函数将他们的参数作为在圆上的位置来解释，0表示在圆的最右边，顺时针走一圈就是2pi。Math.cos告诉你对应给定位置的点的x坐标，Math.sin对应y坐标。大于2pi或者小于0的位置（或角度）是合法的。a+2pi和a指的是同样的角度。

这种量度角度的单位叫做弧度——满圆就是2pi弧度，相似于角度制的360°。常数pi可通过Math.PI在JS中读取。

猫的动画代码维护了一个计数器，angle来记录当前动画的角度，并在每次调用animate函数的时候增加。可以随后使用这个角度来计算当前图片元素的位置。top样式通过Math.sin就算并且乘以20，是我们椭圆的垂直半径。left样式基于Math.cos并且乘以了200，让这个椭圆看上去宽一点。

注意样式通常需要单位。在这个例子中，我们在数字后面添加”px”告诉浏览器我们以像素计数（对应厘米，”ems”或者其他单位）。这很容易忘记。使用不带单位的数字将会使得你的样式被忽略——除非数字是0。

总结

JS程序可以通过一个叫做DOM的数据结构和浏览器显示的文档交互。这个数据结构代表了浏览器对这个文档建立的模型，并且JS可以通过修改它来改变显示的文档。

DOM组织得像个树，妻子红的元素根据文档结构有层次低被安排。表示元素的对象由如parentNode和childNodes这样的属性，可被用于在在树中导航。

文档显示的方式可被通过样式来影响，可以通过直接关联样式到节点上，也可以为匹配的节点定义规则。有许多样式属性，如color和display。JS代码可以直接通过它的style属性来修改元素的样式。

JavaScript和浏览器

这本书的下一张将会讨论web浏览器。没有web浏览器，就不会有JS。或者即使有，也没有人会关注它。

web技术从一开始就是分散的，不仅在技术上，它发展的方式也是一样。各种浏览器厂商都以一些特别的、有时考虑不周的方式添加了新功能，这些功能有时会被其他厂商采用，并最终以标准的形式确定下来。

这既是一种祝福，也是一种诅咒。一方面，它允许没有中央方控制一个系统，而是由各方在松散的协作(或偶尔公开的敌对状态下)下进行改进。另一方面，Web开发的随意方式意味着最终的系统并不是内部一致性的光辉典范。它的某些部分完全令人困惑，构思拙劣。

异步编程

计算机的中心，也就是执行组成我们程序独立的步的部分叫做处理器。我们到目前为止所见的程序将会使处理器一直运转知道它们完成工作。修改数字的循环以多快的速度执行极度依赖处理器的速度。

但是许多程序与处理器外的东西交互。例如，它们可能通过计算机网络通讯或者从硬盘上请求数据，这些操作远比从内存中获取慢得多。

当这样的事情发生时，让处理器停转是一件遗憾的事情，存在可以同时做的一些其他的工作。在某种程度上，这是通过操作系统处理的，操作系统将会在多个运行程序间切换处理器。但是当我们想要让单个程序在等待网络请求的同时能够继续运行操作系统就帮不上忙了。

模块

理想的程序有一个如水晶般清澈的结构。他工作的方式很容易去解释，并且每部分都扮演着精心定义的角色。

一个典型的真正的程序是有机增长的。随着新需求的诞生新功能被添加。结构和保留结构是额外的工作。只有在未来，下一次某人继续这项工作的时候才会有回报。所以很容易忽视它并让程序的部分陷入困境。

这导致了两个实践上的问题。首先，理解这样的系统是苦难你的。如果所有事物可以触碰所有其他的事物，很难孤立地去看待某个给定的部分。你被迫要构建对于整个事物的全盘的理解。其次，如果你想要在其他的环境下从这样的程序中使用任何的功能，重写它可能比将其从它的上下文中抽离出来更加容易。

短语“一个大泥球”经常被用于这样巨大无结构的程序。任何事物粘连在一起，当你想要抽取其中一部分时，整个东西就散了，你的手就会变脏。

正则表达式

编程工具和技术以一种混乱的，进化的方式生存和传播。并不总是漂亮的或聪明的那些最后会胜出，而是那些在市场中功能良好或者刚好与另一项成功的技术结合在一起的那些。

这一章，我将会讨论一个这样的工具，正则表达式。正则表达式是一种在字符串数据中描述模式的方式。它们是一个小的独立的语言，并且是JS和许多语言和系统的一部分。

正则表达式是难于对付的，同时又是极度有用的。他们的语法看上去比较神秘，并且JS为它们提供的编程接口难于处理。但是它们是检查和处理字符串很有力的工具。正确理解正则表达式将使你成为一个更高效的程序员。