代碼隨想錄算法訓練營第十七天 | 110. 平衡二叉樹、257. 二叉樹的所有路徑、404. 左葉子之和

[LeetCode] 110. 平衡二叉樹

[LeetCode] 110. 平衡二叉樹文章解釋

[LeetCode] 110. 平衡二叉樹視頻解釋

給定一個二叉樹，判斷它是否是

平衡二叉樹
?
示例 1：
輸入：root = [3,9,20,null,null,15,7]
輸出：true
示例 2：
輸入：root = [1,2,2,3,3,null,null,4,4]
輸出：false
示例 3：
輸入：root = []
輸出：true
提示：

樹中的節點數在范圍 [0, 5000] 內
-10^4 <= Node.val <= 10^4

自己看到題目的第一想法?

??? 1. 什么是平衡二叉樹, 平衡二叉樹的具體定義是什么呢?

看完代碼隨想錄之后的想法

??? 1. 平衡二叉樹的定義: 每一個節點的左子樹和右子樹的高度叉不大于一, 則說當前二叉樹為平衡二叉樹.

??? 2. 根據定義可以很本能的想到使用遞歸法來判斷是否平衡二叉樹. 假設當前節點為 node, 則先計算 node.left 的高度, 再計算 node.right 的高度. 如果 node.left 和 node.right 的差的絕對值大于 1, 則說明當前節點的左右子樹破壞了平衡, 因此整顆樹都不是平衡二叉樹. 此時返回 -1. 如果 node.left 和 node.right 的差的絕對值不大于 1, 則將兩者中的大者加一后, 返回給上一層函數.

??? 3. 一定要記得, 這里是要判斷每一個節點是否平衡, 不是只單單判斷跟節點的左右節點是否高度上滿足平衡條件.

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
// 遞歸法
class Solution {public boolean isBalanced(TreeNode root) {if (root == null) {return true;}int leftHeight = getHeight(root.left);int rightHeight = getHeight(root.right);return leftHeight != -1 && rightHeight != -1 && Math.abs(leftHeight - rightHeight) <= 1;// 這個條件老是忘記}private int getHeight(TreeNode node) {if (node == null) {return 0;}        if (node.left == null && node.right == null) {return 1;} else {int leftHeight = getHeight(node.left);if (leftHeight == -1) { // 這個條件老是忘記return -1;}int rightHeight = getHeight(node.right);if (rightHeight == -1) { // 這個條件老是忘記return rightHeight;}if (Math.abs(leftHeight - rightHeight) > 1) {return -1;} else {return Math.max(leftHeight, rightHeight) + 1;}}}
}

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
// 迭代法
class Solution {public boolean isBalanced(TreeNode root) {if (root == null) {return true;}Stack<TreeNode> nodes = new Stack<>();TreeNode node = null;nodes.push(root);int leftHeight = 0;int rightHeight = 0;while (!nodes.isEmpty()) {node = nodes.pop();leftHeight = getHeight(node.left);rightHeight = getHeight(node.right);if (Math.abs(leftHeight - rightHeight) > 1) {return false;}if (node.right != null) {nodes.push(node.right);}if (node.left != null) {nodes.push(node.left);}}return true;}private int getHeight(TreeNode node) {if (node == null) {return 0;}Stack<TreeNode> nodes = new Stack<>();int maxDepth = 0;int depth = 0;nodes.push(node);while (!nodes.isEmpty()) {node = nodes.pop();if (node != null) {nodes.push(node);nodes.push(null);depth++;if (node.right != null) {nodes.push(node.right);}if (node.left != null) {nodes.push(node.left);}} else {nodes.pop();depth--;}if (maxDepth < depth) {maxDepth = depth;}}return maxDepth;}
}

自己實現過程中遇到哪些困難

??? 1. 遇到了一個定義上理解錯誤的地方. 平衡二叉樹的平衡, 說的是每個節點都是平衡的, 而不單單指跟節點的左右子節點是平衡的. 最極端的例子, 一個跟節點, 左節點開始的每個節點只有左節點, 右節點開始的每個節點只有右節點, 假設跟節點的左右子樹高度都是3, 這時候當前子樹并不是平衡的.

??? 2. 計算平衡二叉樹高度的時候, 老是忘記判斷迭代返回高度值為 -1 的情況. 說明對平衡二叉樹的判斷邏輯還掌握的不夠清楚和徹底. 寫博客的意義更多的是理清思路, 整理架構. 而現在的模式更像是在記流水賬. 需要反思.

[LeetCode] 257. 二叉樹的所有路徑

[LeetCode] 257. 二叉樹的所有路徑文章解釋

[LeetCode] 257. 二叉樹的所有路徑視頻解釋

自己看到題目的第一想法

解決的思路:

??? 1. 首先, 需要遍歷整個二叉樹.

??? 2. 當遇到葉子結點的時候, 記錄一下當前的路徑.

??? 3. 當遇到葉子結點并且記錄過路徑后, 需要將葉子結點從路徑中刪除.

疑惑點:

??? 如何找到當前葉子結點的上一個節點呢, 只有找到上一個節點, 才能繼續遍歷.

看完代碼隨想錄之后的想法

??? 1. 遞歸法: 遞歸法的邏輯就是把所有遍歷到的元素添加到路徑列表里, 同時傳給下一個子節點. 這樣當到達葉子結點時, 葉子結點就知道從根節點到自己的路徑是什么.

??? 2. 迭代法: 通過迭代法遍歷元素,

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/// 遞歸解法1: 效率一般 49.36%
class Solution {public List<String> binaryTreePaths(TreeNode root) {List<String> result = new ArrayList<>();binaryTreePaths(root, new ArrayList<Integer>(), result);return result;}private void binaryTreePaths(TreeNode node, List<Integer> paths, List<String> result) {if (node == null) {return;}paths.add(node.val);StringBuilder strBuilder = new StringBuilder();if (node.left == null && node.right == null) {for (int i = 0; i < paths.size() - 1; i++) {strBuilder.append(paths.get(i) + "->");}strBuilder.append(paths.get(paths.size() - 1));result.add(strBuilder.toString());paths.remove(paths.size() - 1);return;}if (node.left != null) {binaryTreePaths(node.left, paths, result);}if (node.right != null) {binaryTreePaths(node.right, paths, result);}paths.remove(paths.size() - 1);}
}

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/// 遞歸解法 1 的 StringBuilder 優化版: 
class Solution {public List<String> binaryTreePaths(TreeNode root) {List<String> result = new ArrayList<>();binaryTreePaths(root, "", result);return result;}private void binaryTreePaths(TreeNode node, String path, List<String> result) {if (node == null) {return;}StringBuilder strBuilder = new StringBuilder(path);strBuilder.append(node.val);if (node.left == null && node.right == null) {result.add(strBuilder.toString());return;}strBuilder.append("->");if (node.left != null) {binaryTreePaths(node.left, strBuilder.toString(), result);}if (node.right != null) {binaryTreePaths(node.right, strBuilder.toString(), result);}}
}

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/// 迭代法: 49.36%
class Solution {public List<String> binaryTreePaths(TreeNode root) {List<String> result = new ArrayList<>();if (root == null) {return result;}Stack<TreeNode> nodes = new Stack<>();List<Integer> paths = new ArrayList<>();TreeNode node = null;nodes.push(root);while (!nodes.isEmpty()) {node = nodes.pop();if (node != null) {if (node.left == null && node.right == null) {StringBuilder strBuilder = new StringBuilder();for (int i = 0; i < paths.size(); i++) {strBuilder.append(paths.get(i)).append("->");}strBuilder.append(node.val);result.add(strBuilder.toString());}nodes.push(node);nodes.push(null);paths.add(node.val);if (node.right != null) {nodes.push(node.right);}if (node.left != null) {nodes.push(node.left);}} else {nodes.pop();paths.remove(paths.size() - 1);}}return result;}
}

[LeetCode] 404. 左葉子之和

[LeetCode] 404. 左葉子之和文章解釋

[LeetCode] 404. 左葉子之和視頻解釋

自己看到題目的第一想法

??? 先看了視頻, 所以好像沒有什么自己的思考.

??? 1. 遍歷二叉樹, 遇到葉子結點的時候, 判斷一下當前節點是不是左節點, 是的話將值加入到統計中.

??? 2. 遍歷二叉樹的時候不知道當前節點是否是父節點的左節點, 可以采用遞歸的方式, 將當前節點的父節點傳遞下來, 或者用一個變量標記當前節點是否是左節點.

??? 3. 好像整體也沒有很難.

看完代碼隨想錄之后的想法

??? 1. 最核心的部分就是, 如果不使用額外信息的時候. 我們在遞歸三部曲的循環結束條件中, 需要添加對左側葉子結點的判斷.? 即? node.left != null && node.left.left != null && node.left.right != null.

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
// 遞歸解法
class Solution {public int sumOfLeftLeaves(TreeNode root) {if (root == null) {return 0;}int leftTreeSum = 0;int rightTreeSum = 0;if (root.left != null && root.left.left == null && root.left.right == null) {leftTreeSum = root.left.val;} else {leftTreeSum = sumOfLeftLeaves(root.left);}rightTreeSum = sumOfLeftLeaves(root.right);return leftTreeSum + rightTreeSum;}
}

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
// 迭代解法
class Solution {public int sumOfLeftLeaves(TreeNode root) {if (root == null) {return 0;}Stack<TreeNode> nodes = new Stack<>();TreeNode node = null;nodes.push(root);int sum = 0;while (!nodes.isEmpty()) {node = nodes.pop();if (node.right != null) {nodes.push(node.right);}if (node.left != null && node.left.left == null&& node.left.right == null) {sum += node.left.val;} else if (node.left != null) {nodes.push(node.left);}}return sum;}
}