二叉树的深度

题目描述

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

解题思路

深度优先搜索遍历

• 回溯法 + 动态规划，先序遍历，一个 ret 保存当前最优值，一个 tmp 保存当前值

• 递归，其实递归也是用栈实现的。（递归也太 TM 简洁了）

代码

代码 1

import java.util.Stack;
public class Solution {
    public int TreeDepth(TreeNode root) {
        if (root == null)
            return 0;
        Stack<TreeNode> stack = new Stack<>();
        int ret = 0;
        int tmp = 1;
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
                tmp++;
            }
            root = stack.pop();
            tmp--;
            ret = Math.max(ret, tmp);
            root = root.right;
            if (root != null)
                tmp++;
        }
        return ret;
    }
}

代码 2

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