🥈 二叉树的diff算法

function Node(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}
var a1 = new Node('a');
var b1 = new Node('b');
var c1 = new Node('c');
var d1 = new Node('d');
var e1 = new Node('e');
var f1 = new Node('f');
var g1 = new Node('g');
var h1 = new Node('h');
var i1 = new Node('i');
var j1 = new Node('j');
var k1 = new Node('k');
a1.left = b1;
a1.right = c1;
b1.left = d1;
b1.right = e1;
c1.left = f1;
c1.right = g1;
d1.left = h1;
d1.right = i1;
g1.left = j1;
g1.right = k1;
var a2 = new Node('a');
var b2 = new Node('b');
var c2 = new Node('c');
var d2 = new Node('d');
var e2 = new Node('e');
var f2 = new Node('f');
var g2 = new Node('g');
var h2 = new Node('h');
var i2 = new Node('i');
var j2 = new Node('j');
var k2 = new Node('k');
a2.left = b2;
a2.right = c2;
b2.left = d2;
b2.right = e2;
c2.left = f2;
c2.right = g2;
// d2.left = h2; 修改 h 为 hh
d2.left = 'hh';
d2.right = i2;
g2.left = j2;
// g2.right = k2; 删除 k
// 新增了什么，修改了什么，删除了什么
// {type: "新增", origin: null, now: a1}
// {type: "修改", origin: a1, now: a2}
// {type: "删除", origin: a2, now: null}
function diffTree(root1, root2, diffList) {
  if (root1 == root2) return diffList;
  if (root1 == null && root2 != null) {
    // 新增节点
    diffList.push({ type: '新增', origin: null, now: root2 });
  } else if (root1 != null && root2 == null) {
    // 删除节点
    diffList.push({ type: '删除', origin: root1, now: null });
  } else if (root1.value != root2.value) {
    // 相同位置的节点值不同, 修改了节点
    diffList.push({ type: '修改', origin: root1, now: root2 });
    // 在修改节点后继续比较, 因为如果修改的节点后还有修改的节点所有需要继续比较
    diffTree(root1.left, root2.left, diffList);
    diffTree(root1.right, root2.right, diffList);
  } else {
    // 如果都不满足条件就继续比较下一个节点
    diffTree(root1.left, root2.left, diffList);
    diffTree(root1.right, root2.right, diffList);
  }
}
var diffList = [];
diffTree(a1, a2, diffList);
console.log(diffList);