• 博主簡介：努力學習的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;}

💐若有不懂的地方，歡迎隨時在評論區or私信找瑤瑤子交流討論🌺

• Java島冒險記【從小白到大佬之路】
  

• LeetCode每日一題–進擊大廠

• Go語言核心編程
  

• 算法