层序遍历（广度优先搜索）
要点：
- 由于遍历顺序与处理顺序不一致，故用队列保存遍历的元素
- 用size记录每一层的遍历的元素
- 抛出首元素，将左右子节点放入队列，以此类推
var levelOrder = function(root) {
let queue=[]
let res=[]
queue.push(root)
if(root === null) {
return res;
}
while(queue.length) {
let size = queue.length
let curArr=[]
while(size--){
let node = queue.shift()
curArr.push(node.val)
if(node.left) queue.push(node.left)
if(node.right) queue.push(node.right)
}
res.push(curArr)
}
return res
};
翻转二叉树
力扣题目
思路：遍历的过程中去翻转每一个节点的左右孩子就可以达到整体翻转的效果。
- 递归法
最好用前序遍历，后序遍历。
//前序遍历
var invertTree = function(root) {
if(!root) return null
//交换
const temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left)
invertTree(root.right)
return root
};
- 迭代法（待补充）
对称二叉树
力扣题目
只能使用后序遍历；因为只有这样才能将子节点的信息返回给父节点。
拓展：什么时候才用后序遍历？只有在父节点需要子节点信息的时候。
递归三部曲：
- 确定返回值，参数
- 确定终止条件
- 递归逻辑
终止条件：
- 左空、右空
- 左空，右不空
- 左不空，右空
- 值不等
var isSymmetric = function(root) {
return compare(root.left,root.right)
};
function compare(left,right){
//左空，右空
if(!left && !right) return true
//左空，右不空
if(!left && right) return false
//左不空，右空
if(left && !right) return false
//值不等
if(left.val !== right.val) return false
//比较外层元素
let outside = compare(left.left,right.right)
// 比较内层元素
let inside = compare(left.right,right.left)
let result = outside && inside
return result
}
