【数据结构】二叉树篇| 纲领思路02+刷题

在这里插入图片描述

博主简介：努力学习的22级计算机科学与技术本科生一枚🌸
博主主页： @是瑶瑶子啦
每日一言🌼: 所谓自由，不是随心所欲，而是自我主宰。——康德

一、前言

二叉树的刷题思路和纲领在这篇：【数据结构】二叉树篇| 纲领&思路01+刷题已经给出，这篇主要还是刷题，进行巩固

🍊 不过新增了“二叉树的层序遍历”（第二题），我个人暂时认为它不属于前面所讲纲领两个模式的任何一个，所以我将它单独提出来。

二、刷题

1、翻转二叉树

🔗226. 翻转二叉树

在这里插入图片描述

👧🏻思路：分解成子问题,根节点的左子树 = 根节点右子树翻转后；根节点的右子树 = 根节点右子树翻转后
🙇🏻‍♀️代码：

// 定义：将以 root 为根的这棵二叉树翻转，返回翻转后的二叉树的根节点
TreeNode invertTree(TreeNode root) {if (root == null) {return null;}// 利用函数定义，先翻转左右子树TreeNode left = invertTree(root.left);TreeNode right = invertTree(root.right);// 然后交换左右子节点root.left = right;root.right = left;// 和定义逻辑自恰：以 root 为根的这棵二叉树已经被翻转，返回 rootreturn root;
}

2、二叉树的层序遍历✨

🔗116. 填充每个节点的下一个右侧节点指针
在这里插入图片描述

public Node connect(Node root) {if(root == null){return root;}Queue<Node> q = new LinkedList<>();//创建一个辅助队列q.offer(root);while(!q.isEmpty()){int size = q.size();//当前层次的节点个数for(int i = 0; i < size; size--){//遍历这一层节点Node cur = q.poll();//连接next节点if(i < size-1){cur.next = q.peek();}if(cur.left!= null){q.offer(cur.left);}if(cur.right!=null){q.offer(cur.right);}}}return root;}

3、二叉树展开为链表

🔗114. 二叉树展开为链表

👧🏻思路：后续遍历！在后序位置进行连接即可

至于如何把 root 的左右子树拉平，不用你操心，flatten 函数的定义就是这样，交给他做就行了。

 public void flatten(TreeNode root) {if(root == null){return;}//1、先将左右子树拉平flatten(root.left);flatten(root.right);/****后序遍历位置****/// 左右子树已经被拉平成一条链表TreeNode left = root.left;TreeNode right = root.right;//2进行连接,先把root和left连接成一个链表root.left = null;root.right = left;//3、将原先的右子树接到当前右子树的末端TreeNode p = root;while(p.right!=null){p = p.right;}p.right = right;}