【数据结构和算法】递归，BFS，DFS3种解决方式

1，递归

这题最容易想到的就是递归，啥叫“递归”，也就是下面这张图 开个玩笑，我们画个图来看下 原理很简单，代码如下

 public int TreeDepth(TreeNode root) {
        return root==null? 0 : Math.max(TreeDepth(root.left), TreeDepth(root.right))+1;
    }

看一下运行结果

2，BFS

BFS的实现原理就是一层层遍历，统计一下总共有多少层，我们来画个图分析一下。 代码如下

    public int TreeDepth(TreeNode root) {
        if (root == null)
            return 0;
        //创建一个队列
        Deque<treenode> deque = new LinkedList&lt;&gt;();
        deque.push(root);
        int count = 0;
        while (!deque.isEmpty()) {
            //每一层的个数
            int size = deque.size();
            while (size-- &gt; 0) {
                TreeNode cur = deque.pop();
                if (cur.left != null)
                    deque.addLast(cur.left);
                if (cur.right != null)
                    deque.addLast(cur.right);
            }
            count++;
        }
        return count;
    }

我们再来看一下运行时间，显然效率不是很高

3，DFS

我们可以使用两个栈，一个记录节点的stack栈，一个记录节点所在层数的level栈，stack中每个节点在level中都会有一个对应的值，并且他们是同时出栈，同时入栈

    public int TreeDepth(TreeNode root) {
        if (root == null)
            return 0;
        //stack记录的是节点，而level中的元素和stack中的元素
        //是同时入栈同时出栈，并且level记录的是节点在第几层
        Stack<treenode> stack = new Stack&lt;&gt;();
        Stack<integer> level = new Stack&lt;&gt;();
        stack.push(root);
        level.push(1);
        int max = 0;
        while (!stack.isEmpty()) {
            //stack中的元素和level中的元素同时出栈
            TreeNode node = stack.pop();
            int temp = level.pop();
            max = Math.max(temp, max);
            if (node.left != null) {
                //同时入栈
                stack.push(node.left);
                level.push(temp + 1);
            }
            if (node.right != null) {
                //同时入栈
                stack.push(node.right);
                level.push(temp + 1);
            }
        }
        return max;
    }

运行结果

如果觉得有用就给个赞吧，还可以关注我的《牛客博客》查看更多的详细题解