104.二叉树的最大深度
题目链接：力扣
思路
1、求高度使用的是后序遍历
后序遍历：（左右中）是一种自上而下的方法，根节点想知道自己的最大告诉的时候，让左右子树去统计，左右子树让分别让自己的左右子树去统计，以此类推。叶子节点下面的空节点返回来说自己是0，叶子节点加上自己的1返回给父节点，父节点再去比较自己左右节点的最大值
2、求深度使用的是前序遍历
前序遍历：（中左右）是一种自上而下的方法
但是这道题目让我们求的是二叉树的最大深度，根节点的高度其实就是二叉树的最大深度，这是这道题目的关键所在，那么我们就可以使用后序遍历求出最大深度
二叉树的最大深度
后序遍历求根的最大高度(递归法)
第一步：确定参数类型和返回值
第二步：确定终止条件
第三步：确定单层的逻辑（按照左右中的顺序进行处理）
class Solution { public int maxDepth(TreeNode root) { if (root == null) { return 0; } int leftHeight = maxDepth(root.left); // 左子树的最大高度 int rightHeight = maxDepth(root.right); // 右子树的最大高度 int maxHeight = 1 + Math.max(leftHeight,rightHeight); // 得到中间节点的最大深度 return maxHeight; } }
前序遍历求最大深度(递归法)
采取中左右的前序遍历 涉及回溯思想
class Solution { /** * 递归法(求深度法) */ //定义最大深度 int maxnum = 0; public int maxDepth(TreeNode root) { ans(root,0); return maxnum; } //递归求解最大深度 void ans(TreeNode tr,int tmp){ if(tr==null) return; tmp++; maxnum = maxnum<tmp?tmp:maxnum; ans(tr.left,tmp); ans(tr.right,tmp); tmp--; } }
// 分解写法 class Solution { int result; public int maxDepth(TreeNode root) { result = 0; if (root == null) { return result; } getDepth(root,1); return result; } public void getDepth (TreeNode root, int depth) { result = depth > result ? depth : result; //中 if (root.left == null && root.right == null) { return; } if (root.left != null) { // 左 depth++; getDepth(root.left,depth); depth--; } if (root.right != null) { // 右 depth++; getDepth(root.right,depth); depth--; } return; } }
迭代法求最大深度(迭代法)
迭代法可以使用层序遍历，循环一层深度加1就可以了，最大深度就是二叉树的层数
迭代法也是一种自上而下的思路，从上往下一层一层去记录
class Solution { public int maxDepth(TreeNode root) { int depth = 0; if (root == null) { return depth; } // 创建队列 Deque<TreeNode> deque = new LinkedList<>(); // 将根节点添加进队列 deque.offer(root); // 开始层序遍历 while (!deque.isEmpty()) { // 获取当前节点的个数 int len = deque.size(); // 此时队列不为空，说明这一层是存在的，深度+1 depth++; // 将这一层的节点弹出，同时将下一层的节点添加进来 for (int i = 0; i < len; i++) { TreeNode node = deque.poll(); if (node.left != null) { deque.offer(node.left); } if (node.right != null) { deque.offer(node.right); } } } return depth; } }
559.n叉树的最大深度
题目链接：力扣
思路
是求二叉树的最大深度的扩展
n叉树的最大深度
递归法
原理和二叉树的最大深度的后序遍历法一样
如果根节点有N个子节点，则这N个子节点对应N个子树。记N个子树的最大深度的最大值为maxChildDepth，则该N叉树的最大深度为maxChildDepth + 1
每个子树的最大深度又可以通过同样的方式进行计算，因此可以采用【深度优先搜索】的方法计算
在计算当前N叉树的最大深度时，可以先递归计算出其每个子树的最大深度，然后再计算出当前N叉树的最大深度
递归访问到空节点结束
class Solution { public int maxDepth(Node root) { if (root == null) { return 0; } int maxChildDepth = 0; if (root.children != null) { for (Node child : root.children) { maxChildDepth = Math.max(maxChildDepth,maxDepth(child)); } } return maxChildDepth + 1; } }
迭代法
层序遍历
class Solution { public int maxDepth(Node root) { if (root == null) { return 0; } // 创建队列 Deque<Node> deque = new ArrayDeque<>(); // 将根节点添加到队列中 deque.offer(root); // 定义深度 int depth = 0; // 开始层序遍历 while (!deque.isEmpty()) { // 获取当前层数的节点个数 int len = deque.size(); // 弹出此层节点，添加对应的孩子节点 while (len-- > 0) { Node node = deque.poll(); for (Node child : node.children) { deque.offer(child); } } depth++; } return depth; } }
