录子训练营DAY15 | 102层序遍历 226.翻转二叉树 101.对称二叉树

102 二叉树的层序遍历

题目链接

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

        var levelOrder = function (root) {
            let res = [];
            if(root==null) return res;
            // 用队列来辅助层序遍历
            let que = [];
            que.push(root);
            while(que.length){
                let len = que.length;
                let row = [];
                while(len--){
                    let top = que.shift();
                    row.push(top.val);
                    top.left && que.push(top.left);
                    top.right && que.push(top.right);
                }
                res.push(row);
            }
            return res;
        };

226.翻转二叉树 

题目链接

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

        var invertTree = function (root) {
            // 首先应该明确的一点是，递归先序遍历，翻转每个节点的左右孩子
            function dfs(root) {
                if(root==null) return root;
                [root.left,root.right]=[root.right,root.left];  // 中
                dfs(root.left); // 左
                dfs(root.right); // 右
            }
            dfs(root);
            return root;
        };

101 对称二叉树

题目链接

给你一个二叉树的根节点 root ， 检查它是否轴对称。

第一遍自己写不是很清楚，稀里糊涂的也ac了，主要思路没有捋清楚。二叉树是否对称，要检查左子树和右子树是不是相互翻转的，遍历的时候要遍历的是左右两个子树。要理解只能通过后续遍历，因为根节点的结果要通过左右节点的比较结果来得到。

        var isSymmetric = function (root) {
            if(root==null) return true;
            // 递归遍历节点是否轴对称
            function dfs(left,right){
                // 终止条件
                if(left==null && right==null) return true;
                if(left==null && right!=null || left!=null && right==null || left.val!=right.val) return false;
                // 这样写不容易理解
                // return dfs(left.left,right.right) && dfs(left.right,right.left);
                let outside = dfs(left.left,right.right);   // 左
                let inside = dfs(left.right,right.left);    // 右
                let isSame = outside && inside;             // 中，由左右得到中的结果
                return isSame;
            }
            return dfs(root.left,root.right);
        };