102. 二叉樹的層序遍歷

題目鏈接：102. 二叉樹的層序遍歷
文檔講解：代碼隨想錄
狀態：dfs沒寫出來，bfs不知道如何分層

import java.util.*;public class BinaryTreeLevelOrderTraversal {// 用于存儲每一層的節點值List<List<Integer>> res = new LinkedList<>();// 使用深度優先搜索 (DFS) 進行層序遍歷public List<List<Integer>> levelOrder(TreeNode root) {if (root != null) {dfs(root, 0); // 從根節點開始，深度為0}return res;}// DFS輔助方法public void dfs(TreeNode root, int depth) {if (root == null) {return; // 如果當前節點為空，直接返回}if (res.size() == depth) {// 如果當前深度沒有對應的列表，創建一個新的列表res.add(new ArrayList<>());}// 將當前節點的值添加到對應深度的列表中res.get(depth).add(root.val);// 遞歸處理左子節點，深度加1dfs(root.left, depth + 1);// 遞歸處理右子節點，深度加1dfs(root.right, depth + 1);}// 使用廣度優先搜索 (BFS) 進行層序遍歷public List<List<Integer>> bfs(TreeNode root) {Deque<TreeNode> queue = new LinkedList<>(); // 使用雙端隊列來存儲節點if (root != null) {queue.addLast(root); // 將根節點加入隊列}while (!queue.isEmpty()) {// 獲取當前層的節點個數.// 重要!!!后面代碼中利用size--處理掉每層的結點后,隊列中剩下的結點就是下一層的結點int size = queue.size(); // 當前層的節點數ArrayList<Integer> list = new ArrayList<>(); // 用于存儲當前層的節點值while (size > 0) {TreeNode node = queue.pollFirst(); // 取出當前層的節點list.add(node.val); // 將節點值加入當前層的列表if (node.left != null) {queue.addLast(node.left); // 將左子節點加入隊列}if (node.right != null) {queue.addLast(node.right); // 將右子節點加入隊列}size--;}res.add(list); // 將當前層的節點值列表加入結果列表}return res;}
}// 定義樹節點類
class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }
}

226.翻轉二叉樹

題目鏈接：226.翻轉二叉樹
文檔講解：代碼隨想錄
狀態：so easy

    // 使用遞歸方式進行二叉樹翻轉public TreeNode invertTree(TreeNode root) {if (root != null) {// 保存當前節點的左子節點TreeNode left = root.left;// 保存當前節點的右子節點TreeNode right = root.right;// 遞歸翻轉右子樹，并將其設為當前節點的左子節點root.left = invertTree(right);// 遞歸翻轉左子樹，并將其設為當前節點的右子節點root.right = invertTree(left);}// 返回翻轉后的根節點return root;}// 使用廣度優先搜索 (BFS) 進行二叉樹翻轉public TreeNode bfs(TreeNode root) {if (root != null) {// 創建一個雙端隊列來存儲節點Deque<TreeNode> deque = new LinkedList<>();// 將根節點加入隊列deque.addLast(root);// 當隊列不為空時，繼續處理while (!deque.isEmpty()) {int size = deque.size(); // 當前層的節點數// 遍歷當前層的所有節點while (size-- > 0) {// 取出當前層的節點TreeNode node = deque.pollFirst();// 翻轉當前節點的左右子節點TreeNode temp = node.left;node.left = node.right;node.right = temp;// 如果左子節點不為空，將其加入隊列if (node.left != null) {deque.add(node.left);}// 如果右子節點不為空，將其加入隊列if (node.right != null) {deque.add(node.right);}}}}// 返回翻轉后的根節點return root;}

101. 對稱二叉樹

題目鏈接：101. 對稱二叉樹
文檔講解：代碼隨想錄
狀態：遞歸寫出來了，迭代沒寫出來

    // 判斷二叉樹是否對稱public boolean isSymmetric(TreeNode root) {if (root == null) {return true; // 如果根節點為空，則認為是對稱的}TreeNode left = root.left;TreeNode right = root.right;// 比較根節點的左右子樹是否對稱return compare(left, right);}// 輔助方法：比較兩個子樹是否對稱public boolean compare(TreeNode left, TreeNode right) {if (left == null && right == null) {return true; // 如果兩個子樹都為空，則對稱} else if (left == null || right == null) {return false; // 如果其中一個子樹為空，則不對稱} else {// 比較左子樹的左子樹與右子樹的右子樹，左子樹的右子樹與右子樹的左子樹，以及當前節點的值是否相等return compare(left.left, right.right) && compare(left.right, right.left) && left.val == right.val;}}

    public boolean isSymmetric(TreeNode root) {if (root == null || (root.left == null && root.right == null)) {return true;}Deque<TreeNode> stack = new LinkedList<>();stack.addLast(root.left);stack.addLast(root.right);while (!stack.isEmpty()) {TreeNode right = stack.pollLast();TreeNode left = stack.pollLast();// 如果兩個節點都為空，繼續下一次循環if (left == null && right == null) {continue;}// 如果一個節點為空，另一個節點不為空，則不對稱if (left == null || right == null) {return false;}// 如果兩個節點的值不相等，則不對稱if (left.val != right.val) {return false;}stack.addLast(left.left);stack.addLast(right.right);stack.addLast(left.right);stack.addLast(right.left);}return true;}