代码随想录训练营Day15|102.二叉树层序遍历, 226.翻

102. 二叉树的层序遍历

解题思路

• 可以用队列模拟层次遍历过程，存储每层的节点，并记录每一层的节点数量 size
• 由于 size 记录的是节点数量，所以遍历队列直到 size，那么为一层的结果集
• 如果当前弹出的节点存在左节点 或 右节点，那么继续添加到队列中，依次类推

var levelOrder = function(root) {
    if (!root) {
        return []
    }
    let size = 1;
    let queue = [root];
    let res = [];
    while (queue.length) {
        let unit = []
        let i = 0;
        size = queue.length;
        while(i < size) {
            let node = queue[0]
            unit.push(node.val)
            queue.shift()
            i++
            node.left && queue.push(node.left)
            node.right && queue.push(node.right)
        }
        res.push(unit)
    }
    return res;
};

226. 翻转二叉树

var invertTree = function(root) {
    if (!root) { return root }
    const overturn = function (root) {
        if (!root) {
            return
        }
        if (root.left || root.right) {
            let temp = root.left
            root.left = root.right
            root.right = temp
        }
        overturn(root.left)
        overturn(root.right)
    }
    overturn(root)
    return root
};

101. 对称二叉树

解题思路

• 对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的
• 要比较的不是左右节点，而是两棵左右子树，比较的是两个子树的里侧和外侧的元素是否相等
• 优先考虑节点可能为null的情况：
  1. 左节点为null，右节点为null，返回true
  2. 左节点为null，右节点不为null，返回false
  3. 左节点不为null，右节点为null，返回false
• 左右节点不为null的情况：
  1. 左右节点都不为null，比较节点值，不相等，返回false
• 比较左子树的左侧，右子树的右侧（外侧是否一一相等）
• 比较左子树的右侧，右子树的左侧（里侧是否一一相等）

var isSymmetric = function(root) {
    if (!root) return true
    const compare = function(left,right) {
        if (left === null && right === null) {
            return true
        } else if (left === null && right !== null) {
            return false
        } else if (left !== null && right === null) {
            return false
        } else if (left.val !== right.val) {
            return false
        }
        let outSide = compare(left.left, right.right)
        let inSide = compare(left.right, right.left)
        return outSide && inSide
    }
    return compare(root.left, root.right)
};