【力扣】二叉树

{
    value: 'a',
    left: {
        value: 'b1',
        left: null,
        right: null
    },
    right: {
        value: 'b2',
        left: {
            value: 'b2-1',
            left: null,
            right: null
        },
        right: {
            value: 'b2-2',
            left: null,
            right: null
        }
    }
}

image.png

创建二叉树

class BinaryTree {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
    // 插入跟节点数据
    insert(data) {
        this.value = data[0];
        data.shift();
        this.insertNode(data, this);
    }
    // 插入子节点
    insertNode(resData, node) {
        let Nodes = [node];
        let i = 0;
        for (let node of Nodes) {
            Nodes.push(node.left = new BinaryTree(resData[i]));
            i += 1;
            if (i === resData.length) return node;
            Nodes.push(node.right = new BinaryTree(resData[i]));
            i += 1;
            if (i === resData.length) return node;
        }
    }
}
const data = ['A','B','C','D','E','F','G',null,'H', 'I', 'J', 'K', 'L', 'M']
let tree = new BinaryTree();
tree.insert(data);

遍历

// 广度优先遍历
function BFS(node) {
    let result = [];
    let queue = [];
    queue.push(node);
    let pointer = 0;
    while(pointer < queue.length) {
        let node = queue[pointer++]; // // 这里不使用 shift 方法（复杂度高），用一个指针代替
        result.push(node.value);
        node.left && queue.push(node.left);
        node.right && queue.push(node.right);
    }
    return result;
}

/*
  广度优先遍历：使用队列实现
*/
function levelOrderTravel(nodeTree) {
  // 如果树为空，结束
  if(!nodeTree) return;
  // 初始化一个队列
  let queue = []
  // 将根节点入队
  queue.push(nodeTree)
  let node = null
  let pointer = 0;
  // 只要队列不为空，继续循环
  while(pointer < queue.length) {
    // 按顺序取出队列中最早入队的节点
    let node = queue[pointer++];
    result.push(node.value);
    // 如果出队节点存在左孩子，就将其左孩子入队
    if(node.left) {
      queue.push(node.left)
    }
    // 如果出队节点存在右孩子，就将其右孩子入队
    if(node.right) {
      queue.push(node.right)
    }
  }
}

// 深度优先遍历
// 前序遍历
function DLR(node, res = []) {
    if(node) {
        res.push(node.value);
        node.left && DLR(node.left, res);
        node.right && DLR(node.right, res);  
    }
    return res;
}
// 中序遍历
function LDR(node, res = []) {
    if(node) {
        node.left && LDR(node.left, res);
        res.push(node.value);
        node.right && LDR(node.right, res);
    }
    return res;
}
// 后序遍历
function LRD(node, res = []) {
    if(node) {
        node.left && LRD(node.left, res);
        node.right && LRD(node.right, res);
        res.push(node.value);
    }
    return res;
}