LeetCode:层序遍历 10
1.思路:
递归实现层序遍历，需要deep记录深度便于数值插入对应层的子序列中。
①确定递归函数的参数和返回值：当前节点及其深度deep
②确定终止条件：当前节点为空时返回
③确定单层递归逻辑：
2.代码实现
1class Solution { 2 List<List<Integer>> resList = new ArrayList<>(); 3 public List<List<Integer>> levelOrder(TreeNode root) { 4 //确定递归参数及返回值 5 levelTraversal(root, 0); 6 return resList; 7 } 8 9 // 确定单层递归逻辑 10 public void levelTraversal(TreeNode root, Integer deep) { 11 if (root == null) { 12 return; 13 } 14 deep++; 15 16 if (resList.size() < deep) { 17 List<Integer> item = new ArrayList<>(); 18 resList.add(item); 19 } 20 resList.get(deep - 1).add(root.val); 21 levelTraversal(root.left, deep); 22 levelTraversal(root.right,deep); 23 } 24}
3.复杂度分析
时间复杂度：O(logn)
空间复杂度：创建了结果集和相应的子模块,O(n)
LeetCode:226.翻转二叉树
1.思路：
翻转二叉树，只需要保证根节点下的所有节点翻转一次即可。
翻转需要遍历到每个节点，因此要考虑遍历顺序，前中后都可以，交换节点语句的位置就是遍历的顺序。
具体依旧是：递归三部曲
前序遍历：从根节点反转
后序遍历：从叶子节点反转
2.代码实现：
1// 后续遍历：遍历到叶子节点，遍历到底部，之后返回的过程中向上去交换。 2class Solution { 3 public TreeNode invertTree(TreeNode root) { 4 // 获取左右节点，遍历交换数值或节点的指向即可 5 // 确定终止条件 6 if (root == null) { 7 return null; 8 } 9 // 自己调用自己，深度遍历 10 invertTree(root.left); 11 invertTree(root.right); 12 13 // 确定递归函数的参数与返回值 14 swapTreeNode(root); 15 return root; 16 17 } 18 // 确定单层递归的逻辑 19 public void swapTreeNode(TreeNode root) { 20 TreeNode tmpNode = root.left; 21 root.left = root.right; 22 root.right = tmpNode; 23 } 24}
1// 前序遍历：直接从根节点进行反转，直到叶子节点结束 2class Solution { 3 public TreeNode invertTree(TreeNode root) { 4 // 获取左右节点，遍历交换数值或节点的指向即可 5 // 确定终止条件 6 if (root == null) { 7 return null; 8 } 9 // 确定递归函数的参数与返回值 10 swapTreeNode(root); 11 // 自己调用自己，深度遍历 12 invertTree(root.left); 13 invertTree(root.right); 14 15 16 return root; 17 18 } 19 // 确定单层递归的逻辑 20 public void swapTreeNode(TreeNode root) { 21 TreeNode tmpNode = root.left; 22 root.left = root.right; 23 root.right = tmpNode; 24 } 25}
3.复杂度分析：
时间复杂度：O(logn)
空间复杂度：O(1)
LeetCode:101.对称二叉树2
101. 对称二叉树 - 力扣（LeetCode）
1.思路：
根绝对称二叉树的特点，进行对称的遍历比较二叉树上的值，分为外侧和内侧两种情况。每种情况下，不对成的条件是，左空右不空、右空左不空、左右均不空但值不相同，最终得到左右均空且前面的值相同。
2.代码实现：
1class Solution { 2 public boolean isSymmetric(TreeNode root) { 3 // 遍历，递归？？什么顺序？？？ 不需要每个数值，排除法排除掉不等的情况 4 // 比较数值，怎么比较？？——左子树左侧和右子树右侧 && 左子树右侧和右子树左侧，两者均为true，则返回true 5 return compare(root.left, root.right); 6 } 7 8 public boolean compare(TreeNode left, TreeNode right) { 9 if (left == null && right != null) { 10 return false; 11 } else if (left != null && right == null) { 12 return false; 13 } else if (left == null && right == null) { 14 return true; 15 } else if (left.val != right.val) { 16 return false; 17 } 18 // 比较外侧值 19 boolean compareOutside = compare(left.left, right.right); 20 // 比较内侧值 21 boolean compareInside = compare(left.right, right.left); 22 return compareOutside && compareInside; 23 }
3.复杂度分析：
时间复杂度：O(logn)
空间复杂度：O(1)
参考：
代码随想录 (programmercarl.com)
