二叉树的各种遍历

先序遍历（深度优先遍历）

// 先序遍历
function inOrderTrave(root, cb) {
  if (root === null) return;
  cb(root);
  inOrderTrave(root.left, cb);
  inOrderTrave(root.right, cb);
}

利用栈实现

function deepFirstSearch(node){
  const nodes = []
  if(node != null){
    var stack = []
    stack.push(node)
    while(stack.length != 0){
      let item = stack.pop()
      nodes.push(item)
      const children = item.children
      if(children && children.length > 0){
        for(let i = children.length - 1; i >= 0; i--){
          stack.push(children[i])
        }
      }
      
    }
  }
  return nodes
}

中序遍历

function inOrderTrave(root, cb) {
  if (root === null) return;
  inOrderTrave(root.left, cb);
  cb(root);
  inOrderTrave(root.right, cb);
}

顺序可以看做是节点映射到平面的顺序

后续遍历

function lastOrderTrave(root, cb) {
  if (root === null) return;
  lastOrderTrave(root.left, cb);
  lastOrderTrave(root.right, cb);
  cb(root);
}

广度优先遍历

从根节点出发，在横向遍历二叉树层段节点的基础上纵向遍历二叉树的层次。

用队列实现: 节点入队列，出队列后判断有无子节点， 有的话从左到右入队列

function breadthFirstSearch(node) {
	const nodes = []
	if (node !== null) {
		let queue = []
		queue.push(node)
		while (queue.length != 0) {
			let item = queue.shift()
			nodes.push(item)
			const children = item.children
			if (children) {
				for (let i = 0, len = children.length; i < len; i++) {
					queue.push(children[i])
				}
			}
		}
	}
	return nodes
}

层序遍历

每次都遍历完一层， 再继续下一层，可以得到一个二维数组， 在这基础之上可以用来解决部分问题

比如有一题leetcode的题目是需要获取一棵树从右边看过去的结果， 也就是每一层的最右边的一个节点

function trave(root) {
  if (!root) return [];
  const result = [];
  const queue = [];
  queue.push(root);
  while (queue.length > 0) {
    let subRes = [];
    // 关键循环
    const len = queue.length;
    for (let i = 0; i < len; i++) {
      const node = queue.shift();
      subRes.push(node.val);
      if (node.left) {
        queue.push(node.left);
      }
      if (node.right) {
        queue.push(node.right);
      }
    }
    result.push(subRes);
  }
  return result;
}

如果不是二叉树， 子元素用children表示

function trave(root, cb) {
  if (!root) return [];
  const result = [];
  const queue = [];
  if (Array.isArray(root)) {
    queue.push(...root);
  } else {
    queue.push(root);
  }
  while (queue.length > 0) {
    let subRes = [];
    // 关键循环
    const len = queue.length;
    for (let i = 0; i < len; i++) {
      const node = queue.shift();
      subRes.push(node.val);
      if (cb) {
        cb(node);
      }
      if (node.children && node.children.length > 0) {
        queue.push(...node.children);
      }
    }
    result.push(subRes);
  }
  return result;
}

从视觉效果从上往下遍历

function traveFromTop2Down(arr, cb) {
  if (arr.length === 0) {
    return;
  }
  for (let i = 0, len = arr.length; i < len; i++) {
    cb(arr[i]);
    if (arr[i].children && arr[i].children.length > 0) {
      traveFromTop2Down(arr[i].children, cb);
    }
  }
}

const tree = [
  {
    id: 0,
    children: [
      {
        id: 1,
        children: [
          {
            id: 2
          },
          {
            id: 3
          },
          {
            id: 4,
            children: [
              {
                id: 5
              }
            ]
          }
        ]
      }
    ]
  },
  {
    id: 6,
    children: [
      {
        id: 7
      }
    ]
  }
];

function trave(arr, cb) {
  if (arr.length === 0) {
    return;
  }
  for (let i = 0, len = arr.length; i < len; i++) {
    cb(arr[i]);
    if (arr[i].children && arr[i].children.length > 0) {
      trave(arr[i].children, cb);
    }
  }
}

const result = [];
trave(tree, node => {
  result.push(node.id);
});
console.log(result); //[0,1,2,3,4,5,6,7]