二叉树的存储

1. 链式存储是二叉树最直观的存储方式
   

2. 数组存储
   

数组存储 转 链表存储

例子:

[1,2,3,4,5,6,null,null,7]

树节点定义

function TreeNode(val, left, right) {
  this.val = val === undefined ? 0 : val
  this.left = left === undefined ? null : left
  this.right = right === undefined ? null : right
}

数组严格表示法

对于严格按照二叉树的结构表示的数组，我们可以利用二叉树的性质很方便地完成转换。这里用到的二叉树性质是：

如果对一棵有 n 个结点的完全二叉树的结点按层序编号，对任一结点 i (1≤i≤n)有：

1. 如果 i=1，则结点 i 是二叉树的根，无双亲；
2. 如果 2i≤n，则结点 i 的左孩子是结点 2i；
3. 如果 2i+1≤n，则结点 i 的右孩子是结点 2i+1

利用该性质，我们用递归即可实现

class TreeNode {
  constructor(data) {
    this.val = data //数据
    this.left = null //左孩
    this.right = null //右孩
  }
}

function createTree(arr, index = 0) {
  if (index > arr.length) {
    return null
  }
  if (arr[index] === null) {
    return null
  }
  const node = new TreeNode(arr[index])
  node.left = createTreeNode(arr, index * 2 + 1)
  node.right = createTreeNode(arr, index * 2 + 2)
  return node
}

四种二叉树遍历方式

二叉树的遍历方式主要有：先序遍历、中序遍历、后序遍历、层次遍历。

先序、中序、后序其实指的是父节点被访问的次序。

若在遍历过程中，父节点先于它的子节点被访问，就是先序遍历；父节点被访问的次序位于左右孩子节点之间，就是中序遍历；访问完左右孩子节点之后再访问父节点，就是后序遍历。

二叉树是否对称

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

  const loop = (node1, node2) => {
    if (!node1 && !node2) return true
    if (!node1 || !node2 || node1.val !== node2.val) return false
    return loop(node1.left, node2.right) && loop(node1.right, node2.left)
  }

  return loop(root.left, root.right)
}