Day 15 | 二叉树的层序遍历、226.翻转二叉树、101.对称二叉树

Leetcode 102.二叉树的层序遍历

题目： 102.二叉树的层序遍历 讲解：https://www.bilibili.com/video/BV1GY4y1u7b2

初始思路

类似于广度优先搜索

代码

var levelOrder = function (root) {
    if (!root) return []
    let queue = []
    let res = []
    queue.push(root)
    while (queue.length) {
        // 记录当前层有多少个节点
        let length = queue.length
        // 存放当前层的节点
        let curLevel = []
        for (let i = 0; i < length; i++){
            // 将这个节点弹出
            let node = queue.shift()
            curLevel.push(node.val)
            // 存放当这个节点的左右节点
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
        // 把每一层结果放到结果数组中
        res.push(curLevel)
    }
    return res
};

感想

1. 看完讲解之后看代码更清晰了。
2. curLevel存放着每一层的节点，queue中是原始队列。

Leetcode 107.二叉树的层序遍历 II

题目：107.二叉树的层序遍历 II

初始思路

这不就是把上一题结果翻转一下吗

代码

var levelOrderBottom = function (root) {
    if (!root) return []
    let queue = []
    let res = []
    queue.push(root)
    while (queue.length) {
        // 记录当前层有多少个节点
        let length = queue.length
        // 存放当前层的节点
        let curLevel = []
        for (let i = 0; i < length; i++){
            // 将这个节点弹出
            let node = queue.shift()
            curLevel.push(node.val)
            // 存放当这个节点的左右节点
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
        // 把每一层结果放到结果数组中
        res.push(curLevel)
    }
    return res.reverse()
};

感想

1. 还真是！

Leetcode 199.二叉树的右视图

题目：199.二叉树的右视图

初始思路

我觉得也可以用深度优先搜索，从右子树开始递归遍历

代码

var rightSideView = function (root) {
    if (!root) return []
    let queue = []
    let res = []
    queue.push(root)
    while (queue.length) {
        // 记录当前层有多少个节点
        let length = queue.length
        for (let i = 0; i < length; i++){
            // 将这个节点弹出
            let node = queue.shift()
            if (i === length - 1) {
                // 不影响层序遍历
                // 只有当走到了这层的最后一个节点的时候再加入结果中
                res.push(node.val)
            }
            // 存放当这个节点的左右节点
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
    }
    return res
};

感想

1. 深度优先搜索的题解：https://leetcode.cn/problems/binary-tree-right-side-view/solution/javascriptban-jie-ti-si-lu-by-ityou-o-lkl1/
2. 用广度优先搜索的话，相比前两题：结果res保存的是节点，不是数组了，所以不用curLevel了。在遍历的时候判断到了最后一个节点的时候加入res

Leetcode 637.二叉树的层平均值

题目：637.二叉树的层平均值

初始思路

OK，层序遍历的时候顺便计算一下平均值。

代码

var averageOfLevels = function (root) {
    if (!root) return []
    let queue = []
    let res = []
    queue.push(root)
    while (queue.length) {
        // 记录当前层有多少个节点
        let length = queue.length
        // 存放当前层的节点
        let curLevel = []
        for (let i = 0; i < length; i++) {
            // 将这个节点弹出
            let node = queue.shift()
            curLevel.push(node.val)
            // 存放当这个节点的左右节点
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
        // 求平均值
        let s = curLevel.reduce((sum, curVal) => {
            return sum + curVal
        }, 0)
        // 把每一层结果放到结果数组中
        res.push(s / curLevel.length)
    }
    return res
};

感想

1. 还复习了一下reduce的使用
2. 本质就是第一题的改造

Leetcode 429.N 叉树的层序遍历

题目：429.N 叉树的层序遍历

初始思路

本质还是第一题的改造，但是看Node的定义可以知道，没有left和right了，只有children

代码

var levelOrder = function (root) {
    if (!root) return []
    let queue = []
    let res = []
    queue.push(root)
    while (queue.length) {
        // 记录当前层有多少个节点
        let length = queue.length
        // 存放当前层的节点
        let curLevel = []
        for (let i = 0; i < length; i++){
            // 将这个节点弹出
            let node = queue.shift()
            curLevel.push(node.val)
            // 这里做出改造，遍历children节点
            for (let item of node.children) {
                if (item) queue.push(item)
            }
        }
        // 把每一层结果放到结果数组中
        res.push(curLevel)
    }
    return res
};

感想

1. 把遍历左右节点改成遍历children节点即可。

Leetcode 515.在每个树行中找最大值

题目：515.在每个树行中找最大值

初始思路

套路题

代码

var largestValues = function (root) {
    if (!root) return []
    let queue = []
    let res = []
    queue.push(root)
    while (queue.length) {
        // 假设初始值是第一个元素
        let max = queue[0].val
        // 记录当前层有多少个节点
        let length = queue.length
        // 存放当前层的节点
        let curLevel = []
        for (let i = 0; i < length; i++) {
            // 将这个节点弹出
            let node = queue.shift()
            max = max > node.val ? max : node.val
            // 存放当这个节点的左右节点
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
        // 把每一层结果放到结果数组中
        res.push(max)
    }
    return res
};

感想

1. 本来用的是Math.max()对每一行的curLevel求最大值，但是应该是有null的原因，求出来是NaN
2. 还是在遍历的时候直接求吧

Leetcode 116.填充每个节点的下一个右侧节点指针

题目：116.填充每个节点的下一个右侧节点指针

初始思路

不是纯改模板了

代码

var connect = function (root) {
    if (!root) return root
    let queue = []
    queue.push(root)
    while (queue.length) {
        // 记录当前层有多少节点
        let length = queue.length
        for (let i = 0; i < length; i++) {
            // 将这个节点弹出
            let node = queue.shift()
            if (i < length - 1) {
                // 当节点不是这层最后一个的时候，弹出的时候next指向下一个节点即可
                // 因为next默认为null，不需要对最后一个节点做特殊处理
                node.next = queue[0]
            }
            // 存放当这个节点的左右节点
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
    }
    return root
};

感想

1. 当节点不是这层最后一个的时候，弹出的时候next指向下一个节点即可。因为next默认为null，不需要对最后一个节点做特殊处理
2. 被root为空坑了一把，不能返回空数组，要返回root。因为返回值类型是Node！

Leetcode 117.填充每个节点的下一个右侧节点指针 II

题目：117.填充每个节点的下一个右侧节点指针 II

初始思路

恩？上一题是满二叉树，这题不是满二叉树而已，没有任何区别吧。。。

代码

 var connect = function(root) {
    if (!root) return root
    let queue = []
    queue.push(root)
    while (queue.length) {
        // 记录当前层有多少节点
        let length = queue.length
        for (let i = 0; i < length; i++) {
            // 将这个节点弹出
            let node = queue.shift()
            if (i < length - 1) {
                // 当节点不是这层最后一个的时候，弹出的时候next指向下一个节点即可
                // 因为next默认为null，不需要对最后一个节点做特殊处理
                node.next = queue[0]
            }
            // 存放当这个节点的左右节点
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
    }
    return root
};

感想

1. 跟上一道题一样的代码，但是LeetCode就是过不去。而且黏贴别人的代码也报一样的错。很难不怀疑是不是LeetCode的问题。
2. 语言换成TypeScript通过了。好吧！

Leetcode 104.二叉树的最大深度

题目：104.二叉树的最大深度

初始思路

在遍历的时候同时记录层数。最大的深度就是二叉树的层数。

代码

 var maxDepth = function(root) {
    if (!root) return 0
    let queue = []
    let res = []
    queue.push(root)
    // 记录深度
    let depth = 0
    while (queue.length) {
        // 记录当前层有多少个节点
        let length = queue.length
        depth++
        for (let i = 0; i < length; i++){
            // 将这个节点弹出
            let node = queue.shift()
            // 存放当这个节点的左右节点
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
    }
    return depth
};

感想

1. root判空记得返回0，不是空数组。

Leetcode 111.二叉树的最小深度

题目：111.二叉树的最小深度

初始思路

比上一题多一个判断什么时候结束

代码

var minDepth = function (root) {
    if (!root) return 0
    let queue = []
    let res = []
    queue.push(root)
    // 记录深度
    let depth = 0
    while (queue.length) {
        // 记录当前层有多少个节点
        let length = queue.length
        depth++
        for (let i = 0; i < length; i++){
            // 将这个节点弹出
            let node = queue.shift()
            if (node.left == null && node.right == null) {
                // 如果左右节点都为空，则该节点深度最小
                return depth
            }
            // 存放当这个节点的左右节点
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
    }
    return depth
};

感想

1. 如果左右节点都为空，则该节点深度最小。直接return，不用继续执行了。
2. 我擦，十题终于做完了、

Leetcode 226.翻转二叉树

题目：226.翻转二叉树 讲解：https://www.bilibili.com/video/BV1sP4y1f7q7

初始思路

写了一天层序遍历，前序差点忘了。

代码

// 递归前序遍历
var invertTree = function (root) {
    if (!root) return null
    // 交换左右节点
    const rightNode = root.right
    root.right = invertTree(root.left)
    root.left = invertTree(rightNode)
    return root
};

// 迭代法前序遍历
var invertTree = function (root) {
    // 交换节点
    const invertNode = function (root, left, right) {
        let temp = left
        left = right
        right = temp
        root.left = left
        root.right = right
    }
    if (!root) return null
    let stack = []
    stack.push(root)
    while (stack.length) {
        let current = stack.pop()
        if (!current) {
            // 以右左中的顺序压栈，以中左右的顺序弹栈
            if (current.right) stack.push(current.right)
            if (current.left) stack.push(current.left)
            stack.push(current)
            stack.push(null)
        } else {
            current = stack.pop()
            invertNode(current, current.left, current.right)
        }
    }
    return root
}

// 层序遍历法
var invertTree = function (root) {
    // 交换节点
    const invertNode = function (root, left, right) {
        let temp = left
        left = right
        right = temp
        root.left = left
        root.right = right
    }
    if (!root) return null
    let queue = []
    queue.push(root)
    while (queue.length) {
        // 记录当前层有多少个节点
        let length = queue.length
        for (let i = 0; i < length; i++){
            // 将这个节点弹出
            let node = queue.shift()
            // 翻转节点
            invertNode(node, node.left, node.right)
            // 存放当这个节点的左右节点
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
    }
    return root
}

感想

1. 原来有这么多写法
2. 递归前序肯定是最简单最好想的。迭代法还是有点复杂。层序 写了一天，感觉挺熟的了。

Leetcode 101.对称二叉树

题目：101.对称二叉树 讲解：https://www.bilibili.com/video/BV1ue4y1Y7Mf

初始思路

真的是简单题？

代码

// 递归
var isSymmetric = function (root) {
    // 1 确定递归的参数 root.left root.right和返回值true false
    const compareNode = function (left, right) {
        // 2 确定终止情况
        if ((left == null && right != null) || (left != null && right == null)) {
            // 左右节点其中一个为空，另一个不是。不对称
            return false
        } else if (left == null && right == null) {
            // 左右都为空。对称
            return true
        } else if (left.val != right.val) {
            // 左右节点不为空，且数值也不相同。不对称
            return false
        }
        // 左右节点都不为空，数值相同，进入以下递归
        // 3 确定单层递归逻辑
        let outside = compareNode(left.left, right.right)
        let inside = compareNode(left.right, right.left)
        return outside && inside
    }
    if (!root) return true
    return compareNode(root.left, root.right)
};

// 队列实现迭代判断
var isSymmetric = function (root) {
    if (!root) return true
    let queue = []
    queue.push(root.left)
    queue.push(root.right)
    while (queue.length) {
        let leftNode = queue.shift()
        let rightNode = queue.shift()
        if (leftNode == null && rightNode == null) {
            continue
        }
        if ((leftNode == null & rightNode != null) || (leftNode != null & rightNode == null) || (rightNode.val !== rightNode.val)) {
            return false
        }
        // 外侧
        queue.push(leftNode.left)
        queue.push(rightNode.right)
        // 里侧
        queue.push(leftNode.right)
        queue.push(rightNode.left)
    }
    return true
}

// 栈实现迭代判断
var isSymmetric = function (root) {
    if (!root) return true
    let stack = []
    stack.push(root.left)
    stack.push(root.right)
    while (stack.length) {
        let rightNode = stack.pop()
        let leftNode = stack.pop()
        if (leftNode == null && rightNode == null) {
            continue
        }
        if ((leftNode == null & rightNode != null) || (leftNode != null & rightNode == null) || (rightNode.val !== rightNode.val)) {
            return false
        }
        // 外侧
        stack.push(leftNode.left)
        stack.push(rightNode.right)
        // 里侧
        stack.push(leftNode.right)
        stack.push(rightNode.left)
    }
    return true
}

感想

1. 要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中。
   外侧：左子树的左节点、右子树的右节点
   里测：左子树的右节点、右子树的左节点
   
2. 后面两种方法的写法其实差不多，调换一下顺序，因为出栈的顺序不一样。
3. 今天这十几道题写了两个半小时。感觉脑子里全是left和right。