110.平衡二叉樹

題目鏈接：110.平衡二叉樹
文檔講講：代碼隨想錄
狀態：還可以

思路：計算左右子樹的深度差，遞歸判斷左右子樹是否符合平衡條件

題解：

    public boolean isBalanced(TreeNode root) {if (root == null) {return true;}int leftLen = getMaxLen(root.left);int rightLen = getMaxLen(root.right);return Math.abs(leftLen - rightLen) <= 1 && isBalanced(root.left) && isBalanced(root.right);}public int getMaxLen(TreeNode node) {if (node == null) {return 0;}int leftLen = getMaxLen(node.left);int rightLen = getMaxLen(node.right);return Math.max(leftLen, rightLen) + 1;}

257. 二叉樹的所有路徑

題目鏈接： 257. 二叉樹的所有路徑
文檔講解：代碼隨想錄
狀態：沒寫出來

思路：前序+回溯的思路，遇到葉子節點收集路徑

遞歸解法：

    public List<String> binaryTreePaths(TreeNode root) {List<String> res = new LinkedList<>();StringBuilder sb = new StringBuilder();getPath(root, res, sb);return res;}public void getPath(TreeNode root, List<String> res, StringBuilder sb) {if (root == null) {return;}int length = sb.length();sb.append(root.val);if (root.left == null && root.right == null) {res.add(sb.toString());} else {sb.append("->");getPath(root.left, res, sb);getPath(root.right, res, sb);}sb.setLength(length); // 恢復StringBuilder的狀態}

迭代解法：

    public List<String> binaryTreePaths(TreeNode root) {List<String> res = new LinkedList<>();if (root == null) {return res;}// 創建雙端隊列來存儲節點和路徑Deque<TreeNode> deque = new LinkedList<>();Deque<String> pathDeque = new LinkedList<>();// 初始節點和路徑deque.addLast(root);pathDeque.addLast(Integer.toString(root.val));while (!deque.isEmpty()) {TreeNode node = deque.pollLast();String path = pathDeque.pollLast();// 如果當前節點是葉子節點，將路徑添加到結果中if (node.left == null && node.right == null) {res.add(path);}// 如果右子節點不為空，添加到隊列中并更新路徑if (node.right != null) {deque.addLast(node.right);pathDeque.addLast(path + "->" + node.right.val);}// 如果左子節點不為空，添加到隊列中并更新路徑if (node.left != null) {deque.addLast(node.left);pathDeque.addLast(path + "->" + node.left.val);}}return res;}

404.左葉子之和

題目鏈接： 404.左葉子之和
文檔講解：代碼隨想錄
狀態：總覺得自己遞歸的思路對的，但是結果就是不對，原來是代碼中筆誤把root.left.right寫成了root.right.right。。。。

遞歸題解：

    public int sumOfLeftLeaves(TreeNode root) {// 如果根節點為空，返回0if (root == null) {return 0;}// 檢查當前節點的左子節點是否為葉子節點if (root.left != null && root.left.left == null && root.left.right == null) {// 如果左子節點是葉子節點，返回左葉子節點的值，加上左子樹和右子樹的左葉子節點值return root.left.val + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);} else {// 如果左子節點不是葉子節點，遞歸遍歷左子樹和右子樹return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);}}

迭代題解：

    public int sumOfLeftLeaves(TreeNode root) {if (root == null) {return 0;}int sum = 0;Deque<TreeNode> deque = new LinkedList<>();deque.addLast(root);while (!deque.isEmpty()) {int size = deque.size();while (size-- > 0) {TreeNode node = deque.pollFirst();if (node.left != null) {if (node.left.left == null && node.left.right == null) {sum += node.left.val;}deque.addLast(node.left);}if (node.right != null) {deque.addLast(node.right);}}}return sum;}