思路指南

数据结构的存储方式

其实只有两种，顺序存储（数组）和链式存储（链表），要有递归的思想，自顶而下，从抽象到具体；

队列、栈：用数组实现，要处理扩容、缩容问题；用链表实现，需要更多内存空间存储节点指针；

图：用二维数组实现，邻接矩阵，判断连通性迅速单图如果稀疏则会耗费时间；链表实现：邻接表，节省空间，但操作效率不够；

散列表：通过散列函数将键映射到一个大数组中，拉链法：链表特性，操作简单但需要额外空间存储指针；线性探查法：数组特性，以便连续寻址，不需要指针存储空间但操作复杂；

树：用数组实现：堆，完全二叉树；链表实现，正常二叉树，二叉搜索树、AVL树、红黑树、区间树、B树；

二者优缺点

数组：紧凑连续存储，可以随机访问，通过索引快速搜索，相对节省空间，但需要一次分别配够空间，若需要扩容，则重新分配空间并拷贝过去，T(n) = O(n)，且每次进行插入与删除时，必须搬移后面所有数据以保持连续，T(n) = O(N)。

链表：元素不连续，靠指针指向下一个元素的位置，故不存在数组的扩容问题；在知道前驱、后驱时操作指针插入、删除的T(n)=O(1)，但同样因为不连续从而不能根据索引计算对应元素地址，无法随机访问，同样会消耗更多存储空间。

基本操作

遍历+访问；具体为：增删改查。

线性的，以for/while迭代为代表；

1
2
3
4
5

void traverse(int[] arr) { 
    for (int i = 0; i < arr.length; i++) { 
        // 迭代访问 arr[i] 
    } 
}

链表遍历框架，兼具迭代与递归

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

/* 基本的单链表节点 */ 
class ListNode { 
    int val; 
    ListNode next; 
}
void traverse(ListNode head) { 
    for (ListNode p = head; p != null; p = p.next) { 
        // 迭代访问 p.val 
    } 
}
void traverse(ListNode head) { 
    // 递归访问 head.val 
    traverse(head.next);
}

二叉树遍历框架：典型的非线性递归遍历结构

1
2
3
4
5
6
7
8
9

/* 基本的⼆叉树节点 */ 
class TreeNode { 
    int val; 
    TreeNode left, right; 
}
void traverse(TreeNode root) { 
    traverse(root.left); 
    traverse(root.right); 
}

N叉树的遍历：非线性递归

1
2
3
4
5
6
7
8
9

/* 基本的 N 叉树节点 */ 
class TreeNode { 
    int val; 
    TreeNode[] children; 
}
void traverse(TreeNode root) { 
    for (TreeNode child : root.children) 
        traverse(child);
}

N叉树的遍历可扩展为图的遍历，如何实现图的环？：用个布尔数组visited做标记。

你就会发现只要涉及递归的问题，都是树的问题；其实很多动态规划问题就是在遍历⼀棵树，你如果对树的遍历操作烂熟于心，起码知道怎么把思路转化成代码，也知道如何提取别⼈解法的核⼼思 路。再看看回溯算法，前⽂回溯算法详解⼲脆直接说了，回溯算法就是个 N 叉 树的前后序遍历问题，没有例外。

medium二叉树刷题（树的核心是递归遍历）

二叉树中序遍历

方法一：基于栈的遍历

1、如果left节点存在，就入栈，然后跳left；

2、如果left和right都不存在，则保存当前节点，然后出栈，并让left等于null；

3、如果right存在，且left不存在，则保存当前节点，然后跳right。

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[]}
 */
// 中序遍历
const inorderTraversal = (root) => {
    let list = [];
    let stack = [];
    let node = root;
    
    while(node || stack.length) {
    // 遍历左子树
      while(node) {
          stack.push(node);
          node = node.left;
      }
        node = stack.pop();
        list.push(node.val);
        node = node.right;
    }
    return list;
}

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

const inorderTraversal = root => {
  let res = [], stack = []
  while (root || stack.length) {
    if (root.left) {
      stack.push(root)；
      root = root.left；
    } else if (!root.left && !root.right) {
      res.push(root.val)；
      root = stack.pop()；
      root && (root.left = null)；
    } else if (root.right) {
      res.push(root.val)；
      root = root.right；
    }
  }
  return res
}

方法二：递归

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

var inorderTraversal = function(root) {
    let arr = [];
    if(!root) return [];

   let nums = [root];
    //递归方法实现
    MiddleOrder(root,arr);
    return arr;
};

function MiddleOrder(root,arr){
    if(root.left){
        MiddleOrder(root.left,arr);
    }
    arr.push(root.val);
    if(root.right){
        MiddleOrder(root.right,arr);
    }
}

前序遍历二叉树

方法一：基于栈的迭代实现

首先根入栈将根节点出栈，将根节点值放入结果数组中

然后遍历左子树、右子树，因为栈是先入后出，所以，我们先右子树入栈，然后左子树入栈

继续出栈（左子树被出栈）…….

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

// 前序遍历
const preorderTraversal = (root) => {
    const list = [];
    const stack = [];
    let node = root;
    
    while (node || stack.length){
        while (node){
            stack.push(node.right);
            list.push(node.val);
            node = node.left;
        }
        node = stack.pop();
    }
    return list;
}

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

// 前序遍历
var preorderTraversal = (root) => {
    let result = []
    var preOrderTraverseNode = (node) => {
        if(node) {
            // 先根节点
            result.push(node.val)
            // 然后遍历左子树
            preOrderTraverseNode(node.left)
            // 再遍历右子树
            preOrderTraverseNode(node.right)
        }
    }
    preOrderTraverseNode(root)
    return result
};

后序遍历二叉树

按照左子树-根-右子树的方式，将其转换成迭代方式。

思路：每到一个节点 A，因为根要最后访问，将其入栈。然后遍历左子树，遍历右子树，最后返回到 A。

但是出现一个问题，无法区分是从左子树返回，还是从右子树返回。

因此，给 A 节点附加一个标记T。在访问其右子树前，T 置为 True。之后子树返回时，当 T 为 True表示从右子树返回，否则从左子树返回。

当 T 为 false 时，表示 A 的左子树遍历完，还要访问右子树。

同时，当 T 为 True 时，表示 A 的两棵子树都遍历过了，要访问 A 了。并且在 A 访问完后，A 这棵子树都访问完成了。

1, 先遍历左节点, 当遍历到末尾节点时, 记录值

2, 然后跳回上一层节点, 顺便让left等于null

3, 再遍历右节点, 同样是遍历到末尾节点时, 记录值

4, 第二次返回时, 让右节点等于null

通过这种人为的方式，不断创造末尾节点值。

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

const postorderTraversal = root => {
  let res = [], stack = [];
  while (root || stack.length) {
    if (root.left) {
      stack.push(root);
      root = root.left;
    } 
    else if (root.right) {
      stack.push(root);
      root = root.right;
    } 
    else {
      res.push(root.val);
      root = stack.pop();
      if (root && root.left) root.left = null;
      else if (root && root.right) root.right = null;
    }
  }
  return res;
}

不同的二叉搜索树

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

思路：动态规划；为了构建一颗二叉搜索树，可以遍历每一个数字i,将其作为树根，并将1…i-1作为左子树，i+1…n作为右子树，接着可以按照同样方式递归构建左右子树。原问题可以分成规模较小的两个子问题，且解可以复用，因此用动态规划处理。

具体步骤：题目要求是计算不同二叉搜索树的个数。为此，我们可以定义两个函数：G(n): 长度为 n 的序列能构成的不同二叉搜索树的个数。F(i, n): 以 i 为根、序列长度为 n 的不同二叉搜索树个数 (1 \leq i \leq n)(1≤i≤n)。可见，G(n) 是我们求解需要的函数。

动态规划问题的关键在于构建状态转移方程。

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

var numTrees = function(n) {
    const G = new Array(n + 1).fill(0);
    G[0] = 1;
    G[1] = 1;

    for (let i = 2; i <= n; ++i) {
        for (let j = 1; j <= i; ++j) {
            G[i] += G[j - 1] * G[i - j];
        }
    }
    return G[n];
};

在本题目的扩展下，如果要求生成所有由1-n节点所组成的二叉搜索树。

和二叉搜索树一的解法不同，一的目的是求数量，而这道题是求具体的解，所以不能从树的规律来简化；利用树的递归特性，采用DFS来递归求解；

n个数组成的二叉树，分为分别以1,2,3…,n为顶点的树；以i为例：f[i]的左边树就是1到i-1个数组成的二叉搜索树，因为左边的节点都比顶点小；f[i]的右边子树就是[i+1]到n的数组成的二叉搜索树，因为右边的节点都比顶点大；左右两侧都是树的数组；组合之后，f[i]的数组组合就得到了。

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

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var generateTrees = function (n) {
    if (n == 0) return [];
    function getTree(s, e) {
        if (s > e) return [null];
        if (s == e) return [new TreeNode(s)];
        var tree = [];
        var i = s;
        while (i <= e) {
            var lefts = getTree(s, i - 1), rights = getTree(i + 1, e);
            while (lefts.length) {
                var left = lefts.pop(), j = 0;
                while (j < rights.length) {
                    var right = rights[j];
                    j++;
                    var node = new TreeNode(i);
                    node.left = left;
                    node.right = right;
                    tree.push(node);
                }
            }
            i++;
        }
        return tree;
    }
    return getTree(1, n);
};

从构建1棵树到构建n棵树，该递归思路其实清晰可见。

验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征：1、节点的左子树只包含小于当前节点的数。2、节点的右子树只包含大于当前节点的数。3、所有左子树和右子树自身必须也是二叉搜索树。

方法一：设计一个递归函数来判断，函数表示考虑以root为跟的子树，其子树所有节点是否都在（l,r）的范围内。不在则直接返回，在的话则继续递归调用其左右子树是否满足。

1
2
3
4
5
6
7
8

const helper = (root, lower, upper)=>{
    if (root == null) return ture;
    if (root.val <= lower || root.val >= upper) return false;
    return helper(root.left, lower, root.val) && helper(root.right, root.val, upper);
}
var isValidBST = function(root) {
    return helper(root, -Infinity, Infinity);
};

方法二：中序遍历，二叉搜索树的中序遍历结果一定是升序序列。

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

var isValidBST = function(root) {
    let stack = [];
    let inorder = -Infinity;

    while (stack.length || root !== null) {
        while (root !== null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
        if (root.val <= inorder) return false;
        inorder = root.val;
        root = root.right;
    }
    return true;
};

对称二叉树

验证一个二叉树是否对称

方法一：递归；左子树和右子树镜像对称则这个树是对称的，1、根节点的值相同；2、一个树的右子树跟另一个树的左子树镜像对称。其实本质跟二叉树相等的递归一样。

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

const isSymmetric = (root) => {
  const check = (left, right) => { 
    if (left == null && right == null) return true;
    if (left && right) {
      return left.val == right.val &&
        check(left.left, right.right) &&
        check(left.right, right.left);
    }
    return false;
  };

  if (root) {
    return check(root.left, root.right);
  } else {
    return true;
  }
};

方法二：BFS广度遍历法；入队列的顺序：1、左子树的左子树，右子树的右子树；2、左子树的右子树，右子树的左子树；出队列的时候，检查两两是否对称。

JS中array类型提供了pop()和push()方法来模仿栈这个数据结构的方法；push()方法接受任意数量的参数，并将其逐个添加到数组尾部，并返回修改后数组的长度；pop()方法则从数组末尾溢出最后一项，减少数组的length值，然后返回溢出的项。

而JS用push()和shift()方法结合来模仿队列；shift()方法溢出数组中的第一项并返回该项，同时将数组长度减一；同时也提供了unshift()方法，能在数组前端添加任意项并返回新数组的长度。因此同时使用unshift()和pop()可以从相反方向模拟数列，在前端添加项，从末端移除项。

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

const isSymmetric = (root) => {
  if (root == null) return true;

  const leftQueue = [root.left];   // 队列存放左子树
  const rightQueue = [root.right]; // 队列存放右子树

  while (leftQueue.length && rightQueue.length) {
    const left = leftQueue.shift();
    const right = rightQueue.shift();
    // 左右子树都为空，没有子节点可入列，continue
    if (left == null && right == null) {
      continue;
    }
    if ((left == null && right) || (left && right == null)) {
      return false;
    }
    if (left.val != right.val) {
      return false;
    }
    leftQueue.push(left.left);
    rightQueue.push(right.right);
    leftQueue.push(left.right);
    rightQueue.push(right.left);
  }
  // 其中一个子树还有节点没遍历，说明不对称
  if (leftQueue.length || leftQueue.length) {
    return false;
  } else {
    return true;
  }
};

方法三：利用两个栈来对递归进行模拟

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

var isSymmetric = (root) => {
  if (!root) return true
  let leftStack = [], rightStack = [] // 维护两个栈
  let curLeft = root.left             // 当前的左子树
  let curRight = root.right           // 当前的右子树
  while (curLeft || curRight || leftStack.length || rightStack.length) {
    while (curLeft) {         // 左子树存在
      leftStack.push(curLeft) // 推入leftStack栈
      curLeft = curLeft.left  // 不断将左子树入栈
    }
    while (curRight) {          // 右子树存在
      rightStack.push(curRight) // 推入rightStack栈
      curRight = curRight.right // 不断将右子树压入栈
    }
    if (leftStack.length !== rightStack.length) return false
                                // 栈的高度不相等，说明结构不对称
    curLeft = leftStack.pop()   // 栈顶节点出栈，赋给curLeft
    curRight = rightStack.pop() // 栈顶节点出栈，赋给curRight
    if (curLeft.val !== curRight.val) return false
                                // 两个栈出栈的节点值不相等 不对称
    curLeft = curLeft.right     // 考察左子树的right
    curRight = curRight.left    // 考察右子树的left
  }
  return true
}

二叉树的BFS与DFS

DFS：深度优先搜索一般使用递归的方法进行实现。

1
2
3
4
5
6
7

var dfs = (root) => {
    if (root == null){
        return ;
    }
    dfs(root.left);
    dfs(root.right);
}

BFS则是使用队列的数据结构来进行遍历；

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

var dfs = (root) => {
    var queue = [];
    queue.push(root);
    while (queue.length != 0){
        var node = queue.shift();
        if (node.left != null){
            queue.push(node.left);
        }
        if (node.right != null){
            queue.push(node.right);
        }
    }
}

递归的方法其实隐含地使用了系统的栈，不需要自己去维护数据结构；BFS这种独特的遍历方式正式其用于求解层序遍历和最短路径问题的根本原因。

层序遍历与最小路径问题

1、层序遍历；利用BFS遍历二叉树无法区分队列中的节点来自哪一层，因此需要修改下代码记录队列中节点数量n（即这一层的节点数），然后一口气处理该层n个节点。

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

var dfs = (root) => {
    var queue = [], res = [], level = [];
    queue.push(root);
    while (queue.length != 0){
        var n = queue.length;
        for (var i = 0; i < n; i++){
            var node = queue.shift();
            level.push(node.val);
            if (node.left != null){
                queue.push(node.left);
            }
            if (node.right != null){
                queue.push(node.right);
            }
        }
        res.pop(level);
    }
    return res;
}

其实根据上述层序遍历的代码，要实现二叉树层序遍历的反向输出，只需要修改最后res的入队列方式即可，用unshift来代替pop。

2、最短路径问题：在树中一个节点到一个节点的路径是唯一的，但在图中可能有多条路径，找寻哪一条路径最短。在BFS中，距离源点越近的点会先被遍历到。（Dijkstra算法解决的是带权最短路径问题，而BFS解决的是无权最短路径问题）

二叉树的锯齿形层次遍历

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）

思路：典型广度优先题目；广度优先通过队列处理 【深度优先用栈】

1、将一层记录在数组中 并记录数组长度找下一行所有数据将数组首位弹出 将首位的左右节点追在数组后；

2、按照记录的数组长度 将上层的结点全部弹出后 此时数组只剩下下一行结点了 此时就完成了一层的遍历；类似上题 与上题区别 每层输出反向 加个条件即可

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

* @return {number[][]}
 *
var zigzagLevelOrder = function(root) {
  if(root==null)
    return []
  var arr=[root]
  var res=[]
  var go=true
  while(arr.length>0){
    var n=arr.length
    var now=[]
    if(go){
      while(n-->0){
        var node=arr.shift()
        now.push(node.val)
        if(node.left!=null)arr.push(node.left)
        if(node.right!=null)arr.push(node.right)
      }
      res.push(now)
    }else{
      while(n-->0){
        var node=arr.pop()
        now.push(node.val)
        if(node.right!=null)arr.unshift(node.right)
        if(node.left!=null)arr.unshift(node.left)
      }
      res.push(now)
    }
    go=!go
  }
  return res
};

前序跟中序遍历构造二叉树

思路：构建一个二叉树需要构建三部分：root、左子树、右子树；左子树、右子树的构建，又包括：root、左子树、右子树解题关键在于定位出根节点，划分出左右子树，然后 递归 构建左右子树

具体做法：preorder 数组的第一项肯定是根节点 —— 因为前序遍历的顺序是 [根| 左|右 ][根∣左∣右]。由根节点，在 inorder [左 | 根 | 右][左∣根∣右] 中划分出左、右子树的 inorder 序列。
通过 inorder 中左右子树的节点个数，在 preorder 中确定左、右子树的 preorder 序列。得到左、右子树的 preorder 和 inorder 序列，就能递归构建左右子树。

1
2
3
4
5
6
7
8

const buildTree = (preorder, inorder) => {
  if (inorder.length == 0) return null;
  const root = new TreeNode(preorder[0]);
  const mid = inorder.indexOf(preorder[0]);
  root.left = buildTree(preorder.slice(1, mid + 1), inorder.slice(0, mid));
  root.right = buildTree(preorder.slice(mid + 1), inorder.slice(mid + 1));
  return root;
};

优化一:字符串截取性能消耗比较大，没必要每次均将preorder、inorder切割；用两个指针表示即可，写一个接受指针的辅助函数。

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

const buildTree = (preorder, inorder) => {
  const helper = (p_start, p_end, i_start, i_end) => {
    if (p_start > p_end) return null;
    let rootVal = preorder[p_start];    // 根节点的值
    let root = new TreeNode(rootVal);   // 根节点
    let mid = inorder.indexOf(rootVal); // 根节点在inorder的位置
    let leftNum = mid - i_start;        // 左子树的节点数
    root.left = helper(p_start + 1, p_start + leftNum, i_start, mid - 1);
    root.right = helper(p_start + leftNum + 1, p_end, mid + 1, i_end);
    return root;
  };
  return helper(0, preorder.length - 1, 0, inorder.length - 1);
};

再次优化：每次递归都要indexof寻找根节点位置，耗费性能；可提前把inorder数组元素和索引存到hash表中。

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

const buildTree = (preorder, inorder) => {
  const map = new Map();
  for (let i = 0; i < inorder.length; i++) {
    map.set(inorder[i], i);
  }
  const helper = (p_start, p_end, i_start, i_end) => {
    if (p_start > p_end) return null;
    let rootVal = preorder[p_start];    // 根节点的值
    let root = new TreeNode(rootVal);   // 根节点
    let mid = map.get(rootVal);         // 根节点在inorder的位置
    let leftNum = mid - i_start;        // 左子树的节点数
    root.left = helper(p_start + 1, p_start + leftNum, i_start, mid - 1);
    root.right = helper(p_start + leftNum + 1, p_end, mid + 1, i_end);
    return root;
  };
  return helper(0, preorder.length - 1, 0, inorder.length - 1);
};

中序跟后序遍历构造二叉树

通常从先序序列或者后序序列开始，根据不同遍历方法的规律，选择合适的节点构造树。例如：先序序列的 第一个 节点是根节点，然后是它的左孩子，右孩子等等。后序序列的 最后一个 节点是根节点，然后是它的右孩子，左孩子等等。

从先序/后序序列中找到根节点，根据根节点将中序序列分为左子树和右子树。从中序序列中获得的信息是：如果当前子树为空（返回 None），否则继续构造子树。

创建 hashmap 存储中序序列：value -> its index 。

方法 helper 的参数是中序序列中当前子树的左右边界，该方法仅用于检查子树是否为空。下面分析 helper(in_left = 0, in_right = n - 1) 的逻辑：

1、如果 in_left > in_right，说明子树为空，返回 None。

2、选择后序遍历的最后一个节点作为根节点。

3、假设根节点在中序遍历中索引为 index。从 in_left 到 index - 1 属于左子树，从 index + 1 到 in_right 属于右子树。

4、根据后序遍历逻辑，递归创建右子树 helper(index + 1, in_right) 和左子树 helper(in_left, index - 1)。

5、返回根节点 root

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

var buildTree = function(inorder, postorder) {
    let p = i = postorder.length - 1;
    let build = (stop) => {
        if(inorder[i] != stop) {
            let root = new TreeNode(postorder[p--])
            root.right = build(root.val)
            i--
            root.left = build(stop)
            return root
        }
        return null
    }
    return build()
}

翻转二叉树

递归三步法：1、确定递归函数的参数和返回值；2、确定终止条件；3、确定单层递归的逻辑。

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

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    if (root == null) return null;
    const left = invertTree(root.left);
    const right = invertTree(root.right);
    root.left = right;
    root.right = left;
    return root;
};

将有序数组转换为二叉搜索树

该解题的本质不在于二叉搜索树和中序遍历，本质是平衡。

如何满足平衡条件：每次把一组数最中间的位置作为树的头拎起来，剩余的部分平均分两份，剩余的一个随便给左子树或右子树；

1
2
3
4
5
6

def 做一棵树（数组的哪个段落要做成树）：#这个段落用索引表示即可，与具体数字无关
    #假设这个段落叫A吧
    树的根部 = 这个段落A最中间的数字
    树的左边 = 做一棵树（这个段落A的左边部分）
    树的右边 = 做一棵树（这个段落A的右边部分）
    return 这棵树

二叉搜索树中序遍历后正好是一个递增的数组；因此，其实这个树就是我们中序遍历二叉树的结果。因此我们以和中序遍历相反的方式，从中间开始取root进行构建二叉树即可。

#可以看到整个题解只和index有关，和数组里的具体数字无关， #因为题目给出的“有序数列”帮助我们满足了“二叉搜索树”的条件。因此只需要操作index来对节点进行重新构建即可。

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

const sortedArrayToBST = (nums) => {

  const buildBST = (nums, start, end) => {
    if (start > end) {
      return null;
    }
//无符号右移>>>的操作是：丢弃右边指定位数，并左边补上0，因此等于除以2。
    const mid = (start + end) >>> 1;
    const root = new TreeNode(nums[mid]);

    root.left = buildBST(nums, start, mid - 1);
    root.right = buildBST(nums, mid + 1, end);

    return root;
  };
  
  return buildBST(nums, 0, nums.length - 1);
};

二叉树hard题目

恢复二叉搜索树

二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下，恢复这棵树。

找到二叉搜索树中序遍历得到值序列的不满足条件的位置。本方法开辟一个新数组 \textit{nums}nums 来记录中序遍历得到的值序列，然后线性遍历找到两个位置 i和 j，并重新遍历原二叉搜索树修改对应节点的值完成修复，

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

const inorder = (root, nums) => {
    if (root === null) {
        return;
    }
    inorder(root.left, nums);
    nums.push(root.val);
    inorder(root.right, nums);
}

const findTwoSwapped = (nums) => {
    const n = nums.length;
    let x = -1, y = -1;
    for (let i = 0; i < n - 1; ++i) {
        if (nums[i + 1] < nums[i]) {
            y = nums[i + 1];
            if (x === -1) {
                x = nums[i];
            }
            else break;
        }
    }
    return [x, y];
}

const recover = (r, count, x, y) => {
    if (r !== null) {
        if (r.val === x || r.val === y) {
            r.val = r.val === x ? y : x;
            if (--count === 0) {
                return;
            }
        }
        recover(r.left, count, x, y);
        recover(r.right, count, x, y);
    }
}

var recoverTree = function(root) {
    const nums = [];
    inorder(root, nums);
    const [first, second] = findTwoSwapped(nums);
    recover(root, 2, first, second); 
};

HTML定义了网页的内容；CSS 描述了网页的布局；JavaScript确定了网页的行为。

一个完成的JS实现由下面三部分组成：1、核心ECMAScript；2、文档对象模型DOM；2、浏览器对象模型BOM。

1、ECMAScript与Web浏览器没有依赖关系，就是对实现该标准规定的各方面内容的语言的描述；

2、文档对象模型DOM：针对XML但经过扩展用于HTML的应用程序编程接口API；DOM把整个页面映射为一个多层节点结构，HTML页面中每个组成部分都是某种类型的节点，这些节点又包含着不同类型的数据；通过DOM创建的这个表示文档的树形图，开发者获得了控制页面内容和结构的主动权。借助DOM提供的API，开发人员可以自如地删除、添加、替换或修改任何节点。

3、浏览器对象模型BOM：开发人员使用BOM控制浏览器显示的界面以外的部分，

1、使用script元素嵌入JavaScript代码时，只须为script指定type属性，type=”text/javascript”，之后将JS代码直接放在元素内部，且包含在script内部的JS代码将从上至下被解释；即在解释器对script页面内的所有代码求值完以前，页面中其余内容都不会被浏览器加载或显示。

2、如果要通过script元素来包含外部JS文件，那么需要SRC属性，是一个指向外部JS文件的链接；

且带有src属性的script元素不应该在其script和/script标签之间再包含额外的JS代码，如果包含则只会下载并执行外部脚本文件而忽略内部嵌入的代码。

甚至SRC属性可以包含外部域的JS

1
2

<script type="text/javascript" src="example.js" />
<script type="text/javascript" src="http://www.somewhere.com/afile.js"></script>

现代WEB应用一般把全部JS引用放在body元素中页面内容的后面，以免加载时间过长；或者加上defer作为延迟脚本（延迟至html页面加载完毕），加上async作为异步脚本（不让页面等待两个脚本下载、执行，从而异步加载其他内容）。

一般还是尽可能得用外部文件来包含JS代码，可维护性、可缓存、适应未来。

1、基本概念

变量

松散类型变量，定义时用var后跟变量名，该变量可以用于保存任何值；但用var操作符定义的变量将成为定义该变量作用域中得局部变量，如果在函数中定义，则函数退出后便会销毁该变量。省略var操作符时可定义全局变量，但及其不推荐。

数据类型

5种简单得：Undefined（未定义）、Null（空）、Boolean（布尔型）、Number（数值）、String（字符串）；还有一种复杂的：Object（对象），数据类型具有动态性，无需再定义。用typeof操作符来返回给定变量的数据类型。

Undefined：只有一个值undefined，使用var声明变量时未对其初始化；

Null：只有一个值null，逻辑上表示一个空对象指针，因此使用typeof检测null值时会返回object，定义的变量要存储值则先初始化为null，可直接检查该值判断是否已经保存了一个对象的引用。事实上，undefined值派生自null值，因此它们的相等性测试返回true。

Boolean类型：只有两个字面值：true、false，且区分大小写，即True和False不是布尔类型，只是标识符，调用转型函数Boolean（）可以转换成对应的布尔值。

Number类型：表示整型和浮点数值，十进制、八进制（字面值第一位为0）、十六进制（字面值第一位为0X），ECMAScript会适时地自动将浮点型变为整型，对于极大、极小的数可用e来表示法表示的浮点数值表示。数值范围：Number.MIN_VALUE到Number.MAX_VALUE。

NaN：非数值，是一个特殊的数值，用于表示一个本来要返回数值的操作数未返回数值的情况。任何涉及NaN的操作都会返回NaN，因此用isNaN()函数，不能转换成数值的值都会导致该函数返回true，字符串”blue“不能转换成数值，因此返回true。

1
2

var floatNum = 3.125e7
//e表示法表示的数值等于e前面的数乘以10的指数次幂

Number():用于任何数据类型转换成数值；parseInt()：处理整数；parseFloat()：处理浮点数字字符。

String类型：单、双引号没有区别，包含一些转义序列；ECMAScript中字符串不可变，要改变一个字符串，首先要销毁原来的字符串，再用一个包含新值得字符串填充该变量。

toString()方法，返回对应值字符串；String()转型函数。

object类型：对象其实就是一组数据和功能的集合，对象可以通过执行new操作符后跟要创建的对象类型的名称来创建。Object的每个实例都具有下列方法、属性：

constructor:保存着用于创建当前对象的函数，构造函数；

hasOwnProperty(propertyName)：用于检查给定的属性在当前对象实例中是否存在，其中作为参数的属性名propertyName必须以字符串的形式指定；

isPrototypeOf(object)：用于检查传入的对象是否是当前对象的原型；

propertyIsEnumerable(propertyName)：用于检查给定的属性是否能够使用for-in语句来枚举，与hasOwnProperty(propertyName)方法一样，作为参数的属性名必须以字符串形式指定；

toLocaleString()：返回对象的字符串表示，该字符串与执行环境的地区对应；

toString()：返回对象的字符串表示；

valueOf()：返回对象的字符串、数值或布尔值表示。

操作符

一元加操作符：对非数值应用时，该操作符会像Number转型函数一样对这个值执行转换；一元减操作符主要用于表示负数；

位操作符：用于最基本的层次上，即按内存中表示数值的位来操作数据，按位非~；按位与&；按位或 | ;按位异或 ^；左移 <<;有符号的

1、CSS语法

两个主要部分：选择器 + 一条或者多条声明；每条声明由一个属性和一个值组成，属性是希望设置的样式属性，每个属性有一个值。CSS声明总是以分号结束，声明总以大括号括起来。

如果要在HTML元素中设置CSS样式，需要在元素中设置id、class选择器。

id选择器可以为标有特定id的HTML元素指定特定的样式，HTML元素以id属性来设置id选择器，CSS中id选择器以#来定义。

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

<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8"> 
<title>菜鸟教程(runoob.com)</title> 
<style>
#para1
{
    text-align:center;
    color:red;
} 
</style>
</head>

<body>
<p id="para1">Hello World!</p>
<p>这个段落不受该样式的影响。</p>
</body>
</html>

class选择器用于描述一组元素的样式，区别在于class可以在多个元素中使用，

插入CSS

外部样式表：改变一个文件来改变一个站点的外观；每个页面使用 link标签链接到样式表。link标签在文档的头部：而浏览器会从文件mystyle.css中读到样式，并根据它来格式文档。外部样式表可在任何文本编辑器进行编辑，不能包含任何html标签，应该以CSS的扩展名进行保存，

1
2
3

hr {color:sienna;}
p {margin-left:20px;}
body {background-image:url("/images/back40.gif");}

内部样式表：当单个文档需要特殊格式时，可以使用，可用style标签在文档头部定义内部样式表。

1
2
3
4
5
6
7

<head>
<style>
hr {color:sienna;}
p {margin-left:20px;}
body {background-image:url("images/back40.gif");}
</style>
</head>

内联样式：

多重样式：某些属性在不同样式表中被同样的选择器定义，那么属性值将从更具体的样式表中被继承过来。

多重样式优先级：可以在同一个HTML文档内部引用多个外部样式表。优先级如下：内联样式>内部样式>外部样式>浏览器默认样式

CSS背景

背景属性用于定义HTML元素的背景：

background-color：背景颜色；background-image：背景图像；background-repeat:设置背景不平铺；background-position:背景定位；

CSS文本格式

格式：颜色color、对齐方式text-align、文本修饰text-decoration、文本大小写转换text-transform、文本缩进text-indent。

字体：两种类型的字体系列名称，通用字体、特定字体。font-family属性设置文本的字体系列，

CSS链接

四个基本的链接样式实例：

a:link - 正常，未访问过的链接

a:visited - 用户已访问过的链接

a:hover - 当用户鼠标放在链接上时

a:active - 链接被点击的那一刻

CSS盒子模型

所有HTML元素可以看作盒子，在CSS中，box model这一术语是用来设计和布局时使用的，CSS盒模型本质上是一个盒子，封装周围的HTML元素，包括：边框、边距、填充、实际内容。盒模型允许我们在其他元素和周围元素边框之间的空间放置元素。

不同部分的说明：

outline轮廓：绘制于元素周围的一条线，位于边框边缘的外围，起突出元素的作用。

Margin(外边距)** - 清除边框外的区域，外边距是透明的。可以单独改变元素四周边框，也可以一次改变所有属性。

Border(边框)** - 围绕在内边距和内容外的边框，允许一个元素边框的样式和颜色。

Padding(内边距)** - 清除内容周围的区域，内边距是透明的。

Content(内容)** - 盒子的内容，显示文本和图像

CSS分组与嵌套

分组选择器：在样式表中有很多具有相同样式的元素，可使用分组选择器，每个选择器用逗号分隔。

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

<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8"> 
<title>菜鸟教程(runoob.com)</title> 
<style>
h1,h2,p
{
    color:green;
}
</style>
</head>

<body>
<h1>Hello World!</h1>
<h2>Smaller heading!</h2>
<p>This is a paragraph.</p>
</body>
</html>

嵌套选择器：适用于选择器内部的选择器样式，

• p{ }: 为所有 p 元素指定一个样式。
• .marked{ }: 为所有 class=”marked” 的元素指定一个样式。
• .marked p{ }: 为所有 class=”marked” 元素内的 p 元素指定一个样式。
• p.marked{ }: 为所有 class=”marked” 的 p 元素指定一个样式

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

<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8"> 
<title>菜鸟教程(runoob.com)</title> 
<style>
p
{
    color:blue;
    text-align:center;
}
.marked
{
    background-color:red;
}
.marked p
{
    color:white;
}
p.marked{
    text-decoration:underline;
}
</style>
</head>

<body>
<p>这个段落是蓝色文本，居中对齐。</p>
<div class="marked">
<p>这个段落不是蓝色文本。</p>
</div>
<p>所有 class="marked"元素内的 p 元素指定一个样式，但有不同的文本颜色。</p>
    
<p class="marked">带下划线的 p 段落。</p>
</body>
</html>

CSS显示与定位

display元素设置一个元素应如何显示，visibility属性指定一个元素可见还是隐藏。

visibility：hidden可以隐藏某个元素，但隐藏的元素仍需占用与未隐藏之前一样的空间，虽被隐藏但仍旧影响布局。display：none可以隐藏某个元素，且隐藏的元素不会占用任何空间。

块元素：h1(标题)、p（段落）、div（文档中的块级元素）

内联元素：span（文档中的内联元素）、a（书签）

可以随时改变元素的种类，从而使页面以不同的方式进行组合。

Position属性：static（默认位置）、relative（相对正常位置的相对位置）、fixed（相对浏览器是固定位置，即使窗口滚动它也不会滚动）、absolute（绝对定位的元素相对于已定位的父元素，如果没有已定位的父元素，则其位置相对于html）、sticky（粘性定位：依赖于用户的滚动，在relative与fixed之间切换）。

元素的定位与文档流无关，所以可以覆盖页面上其他元素，z-index属性指定了一个元素的堆叠顺序，实现重叠。

CSS布局

overflow属性用于控制内容溢出元素框时显示的方式，在对应的区间内添加滚动条。

float属性会使元素向左或者向右移动，其周围的元素也会重新排列，往往用于图像或者布局。一个浮动元素会尽量向左或向右移动，直至其外边缘碰到包含框或另一个浮动框的边框。

对齐：1、要水平居中对齐一个元素，可使用margin:auto；并设置到元素的宽度放置它溢出到容器的边缘。2、文本居中对齐，可使用text-align：center；3、图片居中对齐：margin：auto；4、左右对齐：使用定位方式，position：absolute；5、左右对齐：使用float方式；6、垂直居中对齐

CSS组合选择符

说明了两个选择器直接的关系，包含了四种组合方式：后代选择器、子元素选择器、相邻兄弟选择器、普通兄弟选择器

CSS伪类、伪元素

添加一些选择器的特殊效果，伪类的语法：selector:pseudo-class {property:value;}；伪元素的语法：selector:pseudo-element {property:value;}

在支持CSS的浏览器中，链接的不同状态可以以不同方式进行显示。

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

<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8"> 
<title>菜鸟教程(runoob.com)</title> 
<style>
a:link {color:#000000;}      /* 未访问链接*/
a:visited {color:#00FF00;}  /* 已访问链接 */
a:hover {color:#FF00FF;}  /* 鼠标移动到链接上 */
a:active {color:#0000FF;}  /* 鼠标点击时 */
</style>
</head>
<body>
<p><b><a href="/css/" target="_blank">这是一个链接</a></b></p>
<p><b>注意：</b> a:hover 必须在 a:link 和 a:visited 之后，需要严格按顺序才能看到效果。</p>
<p><b>注意：</b> a:active 必须在 a:hover 之后。</p>
</body>
</html>

伪类可以和CSS类配合使用，以根据链接的被访问与否来判断链接的颜色。

first-child伪类来选择父类的第一个子元素；lang伪类：有能力为不同的语言定义特殊的规则；

first-line伪元素用于向文本的首行设置特殊样式，first-letter伪元素用于向文本首字母设置特殊样式；before伪元素可以在元素内容前面插入新元素；after伪元素可以在元素的内容后面插入新内容；

CSS各类工具

垂直导航栏实例

1、先用ul、ui元素构建一个链接列表；

2、利用CSS格式在列表中删除边距和填充；

3、只用a元素的样式，建立一个垂直的导航栏；

4、在点击了选项后，可以添加active类来标准哪个选项被选中；

5、在li、a上添加text-align:center来让链接居中，并在border ul上添加border属性来让导航栏有边框；

6、创建一个左边是全屏高度的固定导航条，右边是可滚动的内容；

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>菜鸟教程(runoob.com)</title>
<style>
body {
    margin: 0;
}

ul {
    list-style-type: none;
    margin: 0;
    padding: 0;
    width: 25%;
    background-color: #f1f1f1;
    position: fixed;
    height: 100%;
    overflow: auto;
}

li a {
    display: block;
    color: #000;
    padding: 8px 16px;
    text-decoration: none;
}

li a.active {
    background-color: #4CAF50;
    color: white;
}

li a:hover:not(.active) {
    background-color: #555;
    color: white;
}
</style>
</head>
<body>

<ul>
  <li><a class="active" href="#home">主页</a></li>
  <li><a href="#news">新闻</a></li>
  <li><a href="#contact">联系</a></li>
  <li><a href="#about">关于</a></li>
</ul>

<div style="margin-left:25%;padding:1px 16px;height:1000px;">
  <h2>Fixed Full-height Side Nav</h2>
  <h3>Try to scroll this area, and see how the sidenav sticks to the page</h3>
  <p>Notice that this div element has a left margin of 25%. This is because the side navigation is set to 25% width. If you remove the margin, the sidenav will overlay/sit on top of this div.</p>

  <p>Some text..</p>
  <p>Some text..</p>
  <p>Some text..</p>
  <p>Some text..</p>
  <p>Some text..</p>
  <p>Some text..</p>
  <p>Some text..</p>
</div>

</body>
</html>

水平导航栏实例

1、指定元素，使用float浮动元素；

2、创建一个水平导航条实例，并在鼠标移动到选项之后修改背景颜色，点击选项后添加active类来标准哪个选项被选中；

3、将导航条的最右边选项设置设置右对齐，通过border-right样式来添加分割线

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
46
47
48

<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>菜鸟教程(runoob.com)</title>
<style>
ul {
    list-style-type: none;
    margin: 0;
    padding: 0;
    overflow: hidden;
    border: 1px solid #e7e7e7;
    background-color: #f3f3f3;
}

li {
    float: left;
}

li a {
    display: block;
    color: #666;
    text-align: center;
    padding: 14px 16px;
    text-decoration: none;
}

li a:hover:not(.active) {
    background-color: #ddd;
}

li a.active {
    color: white;
    background-color: #4CAF50;
}
</style>
</head>
<body>

<ul>
  <li><a class="active" href="#home">主页</a></li>
  <li><a href="#news">新闻</a></li>
  <li><a href="#contact">联系</a></li>
  <li><a href="#about">关于</a></li>
</ul>

</body>
</html>

下拉菜单实例

使用CSS创建一个鼠标移上去后显示下拉菜单的效果，

HTML部分：我们可以使用任何的HTML元素来打开下拉菜单，如span、button元素；使用容器元素来创建下拉菜单的内容，并放在你相放的位置；使用div元素来包裹这些元素并使用CSS来设置下拉内容的样式。

CSS部分：.dropddown类使用position:relative，将设置下拉菜单的内容放置在下拉按钮（position:absolute）的右下位置。.dropdown-content类中是实际的下拉菜单，默认是隐藏的，在鼠标移动到指定元素后会显示。:hover选择器将用于用户将鼠标移动到下拉按钮上时显示下拉菜单。

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
46
47
48
49
50
51
52
53
54
55
56

<style>
/* 下拉按钮样式 */
.dropbtn {
    background-color: #4CAF50;
    color: white;
    padding: 16px;
    font-size: 16px;
    border: none;
    cursor: pointer;
}

/* 容器 <div> - 需要定位下拉内容 */
.dropdown {
    position: relative;
    display: inline-block;
}

/* 下拉内容 (默认隐藏) */
.dropdown-content {
    display: none;
    position: absolute;
    background-color: #f9f9f9;
    min-width: 160px;
    box-shadow: 0px 8px 16px 0px rgba(0,0,0,0.2);
}

/* 下拉菜单的链接 */
.dropdown-content a {
    color: black;
    padding: 12px 16px;
    text-decoration: none;
    display: block;
}

/* 鼠标移上去后修改下拉菜单链接颜色 */
.dropdown-content a:hover {background-color: #f1f1f1}

/* 在鼠标移上去后显示下拉菜单 */
.dropdown:hover .dropdown-content {
    display: block;
}

/* 当下拉内容显示后修改下拉按钮的背景颜色 */
.dropdown:hover .dropbtn {
    background-color: #3e8e41;
}
</style>

<div class="dropdown">
  <button class="dropbtn">下拉菜单</button>
  <div class="dropdown-content">
    <a href="#">菜鸟教程 1</a>
    <a href="#">菜鸟教程 2</a>
    <a href="#">菜鸟教程 3</a>
  </div>
</div>

CSS提示工具实例

1、基础提示框，提示框在鼠标移动到指定元素上显示。

HTML使用容器元素（like div）并添加tooltip类，在鼠标移动到div时显示提示信息；提示文本放在内联元素上（span）并使用class=”tooltiptext”。

CSS中tooltip类使用position:relative，提示文本需要设置定位置position:absolute。tooltiptext类用于实际的提示文本，模式为隐藏的，:hover选择器用于鼠标移动到指定元素div时显示的提示。

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

<style>
/* Tooltip 容器 */
.tooltip {
    position: relative;
    display: inline-block;
    border-bottom: 1px dotted black; /* 悬停元素上显示点线 */
}
 
/* Tooltip 文本 */
.tooltip .tooltiptext {
    visibility: hidden;
    width: 120px;
    background-color: black;
    color: #fff;
    text-align: center;
    padding: 5px 0;
    border-radius: 6px;
 
    /* 定位 */
    position: absolute;
    z-index: 1;
}
 
/* 鼠标移动上去后显示提示框 */
.tooltip:hover .tooltiptext {
    visibility: visible;
}
</style>
 
<div class="tooltip">鼠标移动到这
  <span class="tooltiptext">提示文本</span>
</div>

2、定位提示工具：通过修改容器元素的top、left、right值来修改提示框显示的位置；如果想要提示框显示在头部和底部，需要使用margin-left属性，并设置为-60px

3、可以使用CSS伪元素::after以及content属性为提示工具创建一个小箭头标志，箭头由边框组成，但组合起来后提示工具像语音提示框。

1
2
3
4
5
6
7
8
9
10

.tooltip .tooltiptext::after {
    content: " ";
    position: absolute;
    top: 100%; /* 提示工具底部 */
    left: 50%;
    margin-left: -5px;
    border-width: 5px;
    border-style: solid;
    border-color: black transparent transparent transparent;
}

图片廊

1、CSS创建图片廊：

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

<div class="responsive">
  <div class="img">
    <a target="_blank" href="http://static.runoob.com/images/demo/demo1.jpg">
      <img src="http://static.runoob.com/images/demo/demo1.jpg" alt="图片文本描述" width="300" height="200">
    </a>
    <div class="desc">这里添加图片文本描述</div>
  </div>
</div>
 
<div class="responsive">
  <div class="img">
    <a target="_blank" href="http://static.runoob.com/images/demo/demo2.jpg">
      <img src="http://static.runoob.com/images/demo/demo2.jpg" alt="图片文本描述" width="300" height="200">
    </a>
    <div class="desc">这里添加图片文本描述</div>
  </div>
</div>
 
<div class="responsive">
  <div class="img">
    <a target="_blank" href="http://static.runoob.com/images/demo/demo3.jpg">
      <img src="http://static.runoob.com/images/demo/demo3.jpg" alt="图片文本描述" width="300" height="200">
    </a>
    <div class="desc">这里添加图片文本描述</div>
  </div>
</div>
 
<div class="responsive">
  <div class="img">
    <a target="_blank" href="http://static.runoob.com/images/demo/demo4.jpg">
      <img src="http://static.runoob.com/images/demo/demo4.jpg" alt="图片文本描述" width="300" height="200">
    </a>
    <div class="desc">这里添加图片文本描述</div>
  </div>
</div>

2、使用CSS3的媒体查询来创建响应式图片廊

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

<div class="responsive">
  <div class="img">
    <a target="_blank" href="img_fjords.jpg">
      <img src="http://www.runoob.com/wp-content/uploads/2016/04/img_fjords.jpg" alt="Trolltunga Norway" width="300" height="200">
    </a>
    <div class="desc">这里添加图片文本描述</div>
  </div>
</div>
 
 
<div class="responsive">
  <div class="img">
    <a target="_blank" href="img_forest.jpg">
      <img src="http://www.runoob.com/wp-content/uploads/2016/04/img_forest.jpg" alt="Forest" width="600" height="400">
    </a>
    <div class="desc">这里添加图片文本描述</div>
  </div>
</div>
 
<div class="responsive">
  <div class="img">
    <a target="_blank" href="img_lights.jpg">
      <img src="http://www.runoob.com/wp-content/uploads/2016/04/img_lights.jpg" alt="Northern Lights" width="600" height="400">
    </a>
    <div class="desc">这里添加图片文本描述</div>
  </div>
</div>
 
<div class="responsive">
  <div class="img">
    <a target="_blank" href="img_mountains.jpg">
      <img src="http://www.runoob.com/wp-content/uploads/2016/04/img_mountains.jpg" alt="Mountains" width="600" height="400">
    </a>
    <div class="desc">这里添加图片文本描述</div>
  </div>
</div>
 
<div class="clearfix"></div>
 
<div style="padding:6px;">
  
  <h4>重置浏览器大小查看效果</h4>
</div>

CSS3中属性的透明度是opacity，同时可以利用hover属性增加当用户将鼠标悬停在其中一个图像时会发生什么的时间，此时调为opacity=1

1
2
3
4
5
6
7
8
9
10

img
{
  opacity:0.4;
  filter:alpha(opacity=40); /*  IE8 及其更早版本 */
}
img:hover
{
  opacity:1.0;
  filter:alpha(opacity=100); /* IE8 及其更早版本 */
}

透明盒子中的文字：

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

<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<style>
div.background
{
  width:500px;
  height:250px;
  background:url(https://www.runoob.com/images/klematis.jpg) repeat;
  border:2px solid black;
}
div.transbox
{
  width:400px;
  height:180px;
  margin:30px 50px;
  background-color:#ffffff;
  border:1px solid black;
  opacity:0.6;
  filter:alpha(opacity=60); /* IE8 及更早版本 */
}
div.transbox p
{
  margin:30px 40px;
  font-weight:bold;
  color:#000000;
}
</style>
</head>
 
<body>
 
<div class="background">
<div class="transbox">
<p>这些文本在透明框里。这些文本在透明框里。这些文本在透明框里。这些文本在透明框里。这些文本在透明框里。这些文本在透明框里。这些文本在透明框里。这些文本在透明框里。这些文本在透明框里。这些文本在透明框里。这些文本在透明框里。这些文本在透明框里。这些文本在透明框里。
</p>
</div>
</div>
 
</body>
</html>

图像拼合技术：单个图像的集合，多个图像的网页会降低服务器的请求数量，并节省带宽。与其使用三个独立图像不如使用这种单个图像。

1
2
3
4
5
6

img.home
{
width:46px;
height:44px;
background:url(img_navsprites.gif) 0 0;
}

:hover选择器可以运用于所有元素，因此所有元素都可以显示鼠标悬停在元素上的显示效果。

CSS媒体

允许指定文件如何在不同媒体中实现，而一些CSS属性只设计了某些媒体，而其他的属性可用于许多不同的媒体类型。

@media规则允许在相同样式表为不同媒体设置不同的样式

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

@media screen
{
    p.test {font-family:verdana,sans-serif;font-size:14px;}
}
@media print
{
    p.test {font-family:times,serif;font-size:10px;}
}
@media screen,print
{
    p.test {font-weight:bold;}
}

CSS属性选择性

具有特定属性的HTML元素样式不仅仅是class和id，下面的实例改变了标题title=’runoob‘元素的边框样式

1
2
3
4

[title=runoob]
{
    border:5px solid green;
}

表单样式：属性选择器无需使用class或id的形式。

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

input[type="text"]
{
    width:150px;
    display:block;
    margin-bottom:10px;
    background-color:yellow;
}
input[type="button"]
{
    width:120px;
    margin-left:35px;
    display:block;
}

可用CSS属性选择器来渲染HTML的表单元素，使用width属性设置输入框的宽度；使用padding属性可以在输入框中添加内边距；使用border属性可以修改input边框得大小或颜色；使用background-color属性设置输入框得背景颜色；

CSS计数器

CSS计数器根据规则来递增变量，以下实例在页面创建一个计数器，且每个h2元素计数值都会递归，并在每个h2元素前添加Section计数值。

1
2
3
4
5
6
7
8

body {
  counter-reset: section;
}
 
h2::before {
  counter-increment: section;
  content: "Section " counter(section) ": ";
}

嵌套计数器：在每一个h1元素前添加计数值Section，嵌套得计数值则放在h2元素得前面，内容为 主标题计数值、副标题计数值。

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

body {
  counter-reset: section;
}
 
h1 {
  counter-reset: subsection;
}
 
h1::before {
  counter-increment: section;
  content: "Section " counter(section) ". ";
}
 
h2::before {
  counter-increment: subsection;
  content: counter(section) "." counter(subsection) " ";
}

2、CSS网页布局

网页布局一般分为以下几个部分：头部区域、菜单导航区域、内容区域、底部区域。

1、头部区域一般位于整个网页得顶部，用于设置网页得标题或LOGO；

2、菜单导航区域包含了一些链接，引导用户浏览其他页面；

3、内容区域一般有三种形式，1列用于移动端；2列用于平板设备；3列用于PC桌面设备。

4、底部区域在网页的最下方，一般包含版权信息与联系方式；

通过以上的方式，我们创建了一个响应式等页面，

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

* {
  box-sizing: border-box;
}
 
body {
  font-family: Arial;
  padding: 10px;
  background: #f1f1f1;
}
 
/* 头部标题 */
.header {
  padding: 30px;
  text-align: center;
  background: white;
}
 
.header h1 {
  font-size: 50px;
}
 
/* 导航条 */
.topnav {
  overflow: hidden;
  background-color: #333;
}
 
/* 导航条链接 */
.topnav a {
  float: left;
  display: block;
  color: #f2f2f2;
  text-align: center;
  padding: 14px 16px;
  text-decoration: none;
}
 
/* 链接颜色修改 */
.topnav a:hover {
  background-color: #ddd;
  color: black;
}
 
/* 创建两列 */
/* Left column */
.leftcolumn {   
  float: left;
  width: 75%;
}
 
/* 右侧栏 */
.rightcolumn {
  float: left;
  width: 25%;
  background-color: #f1f1f1;
  padding-left: 20px;
}
 
/* 图像部分 */
.fakeimg {
  background-color: #aaa;
  width: 100%;
  padding: 20px;
}
 
/* 文章卡片效果 */
.card {
  background-color: white;
  padding: 20px;
  margin-top: 20px;
}
 
/* 列后面清除浮动 */
.row:after {
  content: "";
  display: table;
  clear: both;
}
 
/* 底部 */
.footer {
  padding: 20px;
  text-align: center;
  background: #ddd;
  margin-top: 20px;
}
 
/* 响应式布局 - 屏幕尺寸小于 800px 时，两列布局改为上下布局 */
@media screen and (max-width: 800px) {
  .leftcolumn, .rightcolumn {   
    width: 100%;
    padding: 0;
  }
}
 
/* 响应式布局 -屏幕尺寸小于 400px 时，导航等布局改为上下布局 */
@media screen and (max-width: 400px) {
  .topnav a {
    float: none;
    width: 100%;
  }
}

3、CSS总结

已经实现了，如何创建样式表来同时控制多重页面的样式和布局，比如如何定位元素、控制元素的可见性和尺寸、设置元素的形状、将一个元素置于另一个元素之后，以及向某些选择器添加特殊的效果，比如；链接。

CSS实例类型索引：runoob.com/css/css-examples.html。

4、CSS3教程

CSS3用于控制网页样式和布局，CSS3被拆分为“模块”，旧规范已拆分为小块，还增加了新的。最重要的CSS3模块如下：选择器、盒模型、背景和边框、文字特效、2D3D转换、动画、多列布局、用户界面。

CSS格式背景

边框：在CSS3中可添加圆角边框，添加阴影框，并作为边界形象而不使用设计程序。border-radius属性用于创建圆角；box-shadow属性用来添加阴影；border-image属性用于创建边框，允许你指定一个图片作为边框，用于创建上文边框的原始图像。

背景：包含新背景属性，提供更大背景元素控制。background-image添加背景图片；background-size指定背景图像大小；background-origin指定背景图像的位置区域；且CSS3允许在元素上添加多个背景图像。background-clip背景裁剪属性是从指定位置开始绘制。

渐变：可在两个或多个指定颜色之间显示平稳的过渡，linear gradients线性渐变：上、下、左、右、对角，radial gradients由中心定义。同样也可以定义一个角度而不用预定义方向：background-image: linear-gradient(angle, color-stop1, color-stop2);同样也可以使用多个颜色节点的定义、支持透明度以创建减弱变淡效果transparent，repeating-linear-gradient()函数用于重复线性渐变。

文本效果：text-shadow文本阴影、box-shadow盒子阴影、也可以在::before和::after两个伪元素中添加阴影效果

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

<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8"> 
<title>菜鸟教程(runoob.com)</title> 
<style>
#boxshadow {
    position: relative;
    -moz-box-shadow: 1px 2px 4px rgba(0, 0, 0,0.5);
    -webkit-box-shadow: 1px 2px 4px rgba(0, 0, 0, .5);
    box-shadow: 1px 2px 4px rgba(0, 0, 0, .5);
    padding: 10px;
    background: white;
}

/* Make the image fit the box */
#boxshadow img {
    width: 100%;
    border: 1px solid #8a4419;
    border-style: inset;
}

#boxshadow::after {
    content: '';
    position: absolute;
    z-index: -1; /* hide shadow behind image */
    -webkit-box-shadow: 0 15px 20px rgba(0, 0, 0, 0.3);
    -moz-box-shadow: 0 15px 20px rgba(0, 0, 0, 0.3);
    box-shadow: 0 15px 20px rgba(0, 0, 0, 0.3);
    width: 70%;
    left: 15%; /* one half of the remaining 30% */
    height: 100px;
    bottom: 0;
}
</style>
</head>
<body>

<div id="boxshadow">
  <img src="rock600x400.jpg" alt="Norway" width="600" height="400">
</div>

</body>
</html>

阴影使用的一个特例是卡片效果，

CSS文本溢出属性Text Overflow指定应向用户如何显示溢出内容；自动换行属性word-wrap允许强制文本换行，即使分裂中间一个字。

CSS3单词拆分换行属性指定换行规则：

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

<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8"> 
<title>菜鸟教程(runoob.com)</title>
<style> 
p.test1
{
    width:9em; 
    border:1px solid #000000;
    word-break:keep-all;
}

p.test2
{
    width:9em; 
    border:1px solid #000000;
    word-break:break-all;
}
</style>
</head>
<body>

<p class="test1"> This paragraph contains some text. This line will-break-at-hyphenates.</p>
<p class="test2"> This paragraph contains some text: The lines will break at any character.</p>

<p><b>注意:</b>  word-break 属性不兼容 Opera.</p>

</body>
</html>

CSS3字体：自己的字体是在@font-face规则中描述定义的，必须首先定义字体的名称然后指向该字体文字文件。

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

<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8"> 
<title>菜鸟教程(runoob.com)</title> 
<style> 
@font-face
{
    font-family: myFirstFont;
    src: url('Sansation_Light.ttf')
        ,url('Sansation_Light.eot'); /* IE9 */
}

div
{
    font-family:myFirstFont;
}
</style>
</head>
<body>

<p><b>注意:</b> Internet Explorer 9 只支持 .eot 格式的字体.</p>

<div>
使用 CSS3,网站终于可以使用字体以外的预先选择“合法”字体
</div>

</body>
</html>

CSS32D、3D转换

CSS3转换可以对元素进行移动、缩放、转动、拉长或拉伸，转换的效果是让某个元素改变形状、大小和位置。

2D变换：

translate()：根据X、Y轴位置给定的参数，从当前元素位置移动；rotate()：在一个给定度数顺时针旋转的元素，参数为负值则为逆时针；scale(）:增减元素的大小；skew()方法：包含两个参数值，分别表示X轴和Y轴倾斜的角度；matrix()方法和2D变换方法合并成一个，有6个参数包含旋转、缩放、移动、倾斜功能；

3D变换：能够将图片视为一个3D的小纸片进行翻转、变换运动，而不只是旋转与改变大小。

rotateX()方法：围绕其在一个给定度数X轴旋转的元素；

rotateY()方法：围绕其在一个给定度数Y轴旋转的元素；

5、CSS3动画

CSS3过渡

元素从一种样式逐渐改变成另一种的效果，指定添加效果的CSS属性、指定效果的持续时间。要添加多个样式的变换效果，添加的属性由逗号分隔。

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

<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8"> 
<title>菜鸟教程(runoob.com)</title>
<style> 
div
{
    width:100px;
    height:100px;
    background:red;
    transition:width 2s;
    -webkit-transition:width 2s; /* Safari */
}

div:hover
{
    width:300px;
}
</style>
</head>
<body>

<p><b>注意：</b>该实例无法在 Internet Explorer 9 及更早 IE 版本上工作。</p>

<div></div>

<p>鼠标移动到 div 元素上，查看过渡效果。</p>

</body>
</html>