代码随想录算法训练营第十二天 | leetcode：二叉树层序遍历,翻转二叉树，对称二叉树

_zzh 的个人博客 / 47 / 0 / 创建于 5个月前 / 更新于 5个月前

Problem: 102. 二叉树的层序遍历

解题方法

借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
把每层节点按层依次入队列，再用变量size记录每层的节点数，这样使用size–就能准确的弹出每层的节点，弹出节点的同时，依次把孩子节点放入队列。直到队列为空，完成遍历。

code

class Solution {

    /**
     * @param TreeNode $root
     * @return Integer[][]
     */
    function levelOrder($root) {
        $res = [];
        if($root == null) return $res;
        $queue = new SplQueue();
        //根节点入队列
        $queue->enqueue($root);
        while(!$queue->isEmpty()){
            //计算当前层的节点数
            $size = $queue->count();
            $nodeArr = [];
            //遍历当前层的节点数
            while($size--){
                //获取节点
                $data = $queue->dequeue();
                //节点值加入数组
                $nodeArr[] = $data->val;
                //把当前节点的左右孩子加入队列
                if($data->left != null) $queue->enqueue($data->left);
                if($data->right != null) $queue->enqueue($data->right);
            }
            $res[] = $nodeArr;
        }
        return $res;
    }
}

Problem: 226. 翻转二叉树

需要注意的点

题目要求返回的是二叉树，不是返回数组。

解题方法

属于层序遍历的一种变形。在弹出节点的时候交换左右孩子节点后再放入队列即可。
把每层节点按层依次入队列，再用变量size记录每层的节点数，这样使用size–就能准确的弹出每层的节点，弹出节点的同时，依次把左右孩子节点交换swap()然后再放入队列。直到队列为空，完成遍历。

code

class Solution {

    /**
     * @param TreeNode $root
     * @return TreeNode
     */
    function invertTree($root) {
        if($root == null) return $root;
        $queue = new SplQueue();
        $queue->enqueue($root);
        while(!$queue->isEmpty()){
            $size = $queue->count();
            while($size--){
                $node = $queue->dequeue();
                //交换左右孩子节点
                $temp = $node->left;
                $node->left = $node->right;
                $node->right = $temp;
                //左右孩子节点入队列，即下一层节点入队列
                if($node->left != null) $queue->enqueue($node->left);
                if($node->right != null) $queue->enqueue($node->right);
            }
        }
        return $root;
    }
}

Problem: 101. 对称二叉树

解题方法

思路：层序遍历中，因为是判断对称，所以对称的话右边子树左节点对应左子树右节点，右边子树右节点对应左子树左节点。
判断对称不用处理根节点。把左右子树根节点依次入队列，判断左节点与右节点是否相等或者是否都为空（都为空也对称）。第一层判断完成之后，按右边子树左节点对应左子树右节点，右边子树右节点对应左子树左节点的规则，依次入栈下一层的左右孩子。

code

class Solution {

    /**
     * @param TreeNode $root
     * @return Boolean
     */
    function isSymmetric($root) {
        if($root == null) return $root;
        $queue = new SplQueue();
        $queue->push($root->left);
        $queue->push($root->right);
        while(!$queue->isEmpty()){
            //队列先进先出，左节点先入队列，所以先出队列的是左节点
            $leftNode = $queue->dequeue();
            $rightNode = $queue->dequeue();

            //如果左右节点都为空，证明还是对称
            if($leftNode == null && $rightNode == null) continue;

            //如果有单独一边节点为空，或者两边的只不相等，则不对称
            if($leftNode == null || $rightNode == null || ($leftNode->val != $rightNode->val)) return false;

            //因为是对称，所以右边子树左节点对应左子树右节点，右边子树右节点对应左子树左节点
            //左节点的左孩子 与 右节点的右孩子依次入队列
            $queue->enqueue($leftNode->left);
            $queue->enqueue($rightNode->right);
            //左节点的右孩子 与 右节点的左孩子依次入队列
            $queue->enqueue($leftNode->right);
            $queue->enqueue($rightNode->left);
        }
        return true;
    }
}