首页 > 代码库 > 算法：二叉树
算法：二叉树
1. Maximum Depth of Binary Tree: https://leetcode.com/problems/maximum-depth-of-binary-tree/
最大深度：
解法1：<Recursive>
1 public class Solution { 2 public int maxDepth(TreeNode root) { 3 if (root == null) return 0; 4 int rst = Math.max(maxDepth(root.left), maxDepth(root.right)); 5 return rst + 1; 6 } 7 }
解法2：<Iterative>（层序遍历思想: queue+size+cnt;）
1 public int maxDepth(TreeNode root) { 2 if(root == null) { 3 return 0; 4 } 5 Queue<TreeNode> queue = new LinkedList<>(); 6 queue.offer(root); 7 int count = 0; 8 while(!queue.isEmpty()) { 9 int size = queue.size(); 10 while(size-- > 0) { 11 TreeNode node = queue.poll(); 12 if(node.left != null) { 13 queue.offer(node.left); 14 } 15 if(node.right != null) { 16 queue.offer(node.right); 17 } 18 } 19 count++; 20 } 21 return count; 22 }
2. Minimum Depth of Binary Tree：https://leetcode.com/problems/minimum-depth-of-binary-tree/
最小深度：
解法1：<Recursice>（左节点为null返回右边的min+1；右节点为null返回左边的min+1；都不为null则返回Math.min()+1;）
1 public class Solution { 2 public int minDepth(TreeNode root) { 3 if (root == null) return 0; 4 if (root.left == null) return minDepth(root.right) + 1; 5 if (root.right == null) return minDepth(root.left) + 1; 6 int rst = Math.min(minDepth(root.left), minDepth(root.right)); 7 return rst + 1; 8 } 9 }
解法2：<Iterative>（层序遍历思想；找到第一个叶节点就返回）
public class Solution { public int minDepth(TreeNode root) { if (root == null) return 0; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int count = 1; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); if (node.left == null && node.right == null) return count; if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } count++; } return count; } }
3. Binary Tree Inorder Traversal：https://leetcode.com/problems/binary-tree-inorder-traversal/
中序遍历：
解法1：<Recursive>(addAll)
public class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> rst = new ArrayList<>(); if (root == null) return rst; rst.addAll(inorderTraversal(root.left)); rst.add(root.val); rst.addAll(inorderTraversal(root.right)); return rst; } }
解法2：<Iterative>
算法：二叉树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。