java 二叉树的深度

以下是Java中求二叉树深度的两种方法：

方法一：递归法

在递归方法中，我们首先检查根节点是否为空。如果为空，说明二叉树为空树，深度为0。然后，我们使用递归的方式分别计算左子树和右子树的最大深度。最后，我们返回左子树和右子树中深度较大的值加1，即为二叉树的最大深度。

public class Solution {
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    //递归版本
    public int TreeDepth(TreeNode root) {
        if(root==null) return 0;
        int nLeft=TreeDepth(root.left);
        int nRight=TreeDepth(root.right);
        return (nLeft>nRight)?(nLeft+1):(nRight+1);
    }
}

方法二：非递归法

在非递归方法中，我们使用一个栈来存储每个节点以及它们的深度。我们首先将根节点和深度0入栈。然后，我们不断从栈中取出节点，如果该节点有左子树或右子树，则将它们和对应的深度入栈。我们不断重复这个过程，直到栈为空。最后，我们返回最大深度。

import java.util.Stack;

public class Solution {
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    //非递归版本
    public int TreeDepth(TreeNode root) {
        if(root==null) return 0;
        Stack<TreeNode> stack=new Stack<>();
        Stack<Integer> depth=new Stack<>();
        stack.push(root);
        depth.push(1);
        int maxDepth=0;
        while(!stack.isEmpty()){
            TreeNode node=stack.pop();
            int d=depth.pop();
            maxDepth=Math.max(maxDepth,d);
            if(node.left!=null){
                stack.push(node.left);
                depth.push(d+1);
            }
            if(node.right!=null){
                stack.push(node.right);
                depth.push(d+1);
            }
        }
        return maxDepth;
    }
}