从上到下打印二叉树|博客系列

# 从上到下打印二叉树

例如有棵树是这样的：

			1
		/		\
  2				3
 /  \    /  \ 
4    6  7		 5

@前端进阶之旅: 代码已经复制到剪贴板

该课树转换为JS代码:

class Node {
  constructor (value, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}
const tree = new Node(1, new Node(2, new Node(4), new Node(6)), new Node(3, new Node(7), new Node(5)));

@前端进阶之旅: 代码已经复制到剪贴板

（为后面三题的前置条件）

# 题目1-不分行从上到下打印

# 题目描述

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

需要输出：

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

@前端进阶之旅: 代码已经复制到剪贴板

# 解题思路

这道题其实很简单啦，看这输出结果，不就是求二叉树的广度遍历吗？

# coding

OK👌，直接开搞：

function print(node) {
  let list = [];
  let stack = [node];
  while (stack.length !== 0) {
    node = stack.shift();
    list.push(node.value);
    if (node.left) stack.push(node.left);
    if (node.right) stack.push(node.right);
  }
  return list;
}
console.log(print(tree));

@前端进阶之旅: 代码已经复制到剪贴板

# 题目2-把二叉树打印成多行

# 题目描述

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

需要输出：

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

@前端进阶之旅: 代码已经复制到剪贴板

# 解题思路

总体来说还是需要使用广度遍历
需要定义一个二维数组result来盛放每一层的结果，也就是最后的输出结果
需要一个数组tempArr来盛放当前这层所有节点的值
需要一个变量来记录当前这层的节点数量currentNums
需要一个变量来记录当前这层的孩子节点的数量childNums
当前层遍历完成后开始遍历孩子节点，currentNums赋值为childNums，childNums赋值为0

# coding

function print (node) {
  let result = [];
  let tempArr = [];
  let currentNums = 1;
  let childNums = 0;
  let stack = [node];
  while (stack.length !== 0) {
    node = stack.shift();
    tempArr.push(node.value);
    if (node.left) {
      stack.push(node.left);
      childNums++;
    }
    if (node.right) {
      stack.push(node.right);
      childNums++;
    }
    currentNums--;
    if (currentNums === 0) {
      currentNums = childNums;
      childNums = 0;
      result.push(tempArr);
      tempArr = [];
    }
  }
  return result;
}

@前端进阶之旅: 代码已经复制到剪贴板

# 题目3-按之字形顺序打印二叉树

# 题目描述

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

需要输出：

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

@前端进阶之旅: 代码已经复制到剪贴板

# 解题思路

解法一

可以将题目2中得到的二维数组处理一下：把偶数层的数组使用reserve逆序排一下就行了。

解法二

每一层是从左到右打印还是从右到左打印是由谁决定的呢？

例如我们定义了一个数组stack用来放某个节点下的子节点。

这里有一颗超级简单的树：

			1
		/		\
  2				3

@前端进阶之旅: 代码已经复制到剪贴板

stack是长[2, 3]或是长[3, 2]，其实只是由push的顺序决定的而已。

若当前层为奇数层，从左到右打印，同时填充下一层，从右到左打印（先填充左孩子节点再填充右孩子节点）。
若当前层为偶数层，从右到左打印，同时填充下一层，从左到右打印（先填充右孩子节点再填充左孩子节点）。

# coding

解法一

function print (node) {
  let result = [];
  let tempArr = [];
  let currentNums = 1;
  let childNums = 0;
  let stack = [node];
  while (stack.length !== 0) {
    node = stack.shift();
    tempArr.push(node.value);
    if (node.left) {
      stack.push(node.left);
      childNums++;
    }
    if (node.right) {
      stack.push(node.right);
      childNums++;
    }
    currentNums--;
    if (currentNums === 0) {
      currentNums = childNums;
      childNums = 0;
      result.push(tempArr);
      tempArr = [];
    }
  }
  result = result.map((arr, idx) => {
    return (idx + 1) % 2 === 0 ? arr.reverse() : arr;
  })
  return result;
}

@前端进阶之旅: 代码已经复制到剪贴板

解法二

function print(node) {
  const result = [];
  const oddStack = [];
  const evenStack = [];
  let temp = [];
  if (node) {
    oddStack.push(node)
    while (oddStack.length !== 0 || evenStack.length !== 0) {
      while (oddStack.length !== 0) {
        const current = oddStack.shift();
        temp.push(current.value);
        if (current.right) {
          evenStack.push(current.right);
        }
        if (current.left) {
          evenStack.push(current.left);
        }
      }
      if (temp.length > 0) {
        result.push(temp);
        temp = [];
      }
      while (evenStack.length !== 0) {
        const current = evenStack.shift();
        temp.push(current.value);
        if (current.left) {
          oddStack.push(current.left)
        }
        if (current.right) {
          oddStack.push(current.right)
        }
      }
      if (temp.length > 0) {
        result.push(temp);
        temp = [];
      }
    }
  }
  return result;
}

@前端进阶之旅: 代码已经复制到剪贴板