队列dq每次只保存一层的元素,使用一个栈st保存下一层的元素。使用bool变量leftToright记录当前层是否是“从左往右”的顺序遍历
在遍历一层元素时:
- 如果是“从左往右”,因为下一层是“从右往左”,所以先将左子节点压栈,再将右子节点压栈
- 如果是“从右往左”,因为下一层是“从左往右”,所以先将右子节点压栈,再将左子节点压栈
在遍历元素时,将元素保存在数组tp中
如果队列dq为空,表示遍历完一层,那么将下一层元素从栈st中弹出,压入队列;改变元素的遍历方向;并将这一层的元素数组tp保存到结果数组res中