代码随想录算法训练营第十二天 | leetcode：二叉树层序遍历,翻转二叉树，对称二叉树
0 / 0 / 创建于 1年前 /
_zzh 的个人博客
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;
}
}本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号