查找二叉树的最大深度

Question

public class TreeNode { 
    int val; 
    TreeNode left; 
    TreeNode right; 
    TreeNode(int x) { val = x; } 
} 

public class Solution { 
    public int maxDepth(TreeNode root) { 
     TreeNode focusNode = root; 
     TreeNode focusNode2 = root; 
     int count = 0; 
     int count1 = 0; 
     boolean a = true; 
     while (a) { 
      if (focusNode != null) { 
       count++; 
       focusNode = focusNode.left; 
      } 
      if (focusNode2 != null) { 
       count++; 
       focusNode2 = focusNode2.right; 
      } else { 
       a = false; 
      } 
     } 
     return Math.max(count,count1); 
    } 
} 

我很困惑为什么我写的代码无法给出预期的输出。而且我也对最大深度的定义感到困惑。仅仅考虑左边排列的所有节点还是排列在右边的所有节点，都会发现最大深度？

Answer 1

我不确定你是在谈论树的高度还是节点的深度。
这里是高度和深度的定义。

节点的高度 - 节点的高度是该节点和叶子之间最长的向下路径上的边的数量。

深度-节点的深度是从节点到树的根节点的边的数量。

   R 
      /\ 
       A B 
      /\/\ 
      C D E F 
       \ 
       G  

例如：
为节点R的深度为0，高度为3
为节点G的深度是3和高度为0

让假设你发现树的高度。
为什么你的程序无法获得你想要的结果？
这是因为你的代码没有遍历树中的所有节点

让我们用树图为例：
在你的循环将首先让focusNode，focusNode2 =节点R

focusNode R> A> C
focusNode2 R> B>˚F>终止

内树中所有子节点没算，如果你的树是不是一个完美的二叉树，那么你会得到错误的答案。

建议你可以阅读如何遍历像预购Travesal
https://en.wikipedia.org/wiki/Tree_traversal

Answer 2

你不是遍历整个树一树的一些算法。你只在最左边和最右边的路径上跑。

通常情况下，递归是你的朋友与二叉树，因为每个节点可以简单地和孤立地处理。

定义为节点类​​方法，即利用这些事实：

• 空孩子的深度为零
• 非空孩子的深度是通过调用发现其​​方法（即递归）
• this节点的深度是其子的深度最大，加1（所以它本身计数）

实现它并在根节点上调用​​以查找树的最大深度。相应实现的递归性质将贯穿整个树。