写程序找出二叉树的深度。

[问答题]

写程序找出二叉树的深度。

查看答案及解析

武培轩

剑指Offer-二叉树的深度

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    /**
     * 递归
     *
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1);
    }
    /**
     * 非递归，层次遍历
     *
     * @param root
     * @return
     */
    public int maxDepth_2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int depth = 0;
        int start = 0;
        int end = 1;
        Queue queue = new LinkedList();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode temp = queue.poll();
            start++;
            if (temp.left != null) {
                queue.offer(temp.left);
            }
            if (temp.right != null) {
                queue.offer(temp.right);
            }
            if (start == end) {
                start = 0;
                end = queue.size();
                depth++;
            }
        }
        return depth;
    }
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }
}

编辑于 2018-09-12 15:52:03 回复(0)

更多回答

推荐

望童年

一个树的深度等于max(左子树深度，右子树深度)+1。可以使用递归实现。假设节点为定义为

struct Node { 
　　Node* left; 
　　Node* right; 
}; 
int GetDepth(Node* root) { 
　　if (NULL == root) { 
    　　return 0; 
　　} 
　　int left_depth = GetDepth(root->left); 
　　int right_depth = GetDepth(root->right); 
　　return left_depth > right_depth ? left_depth + 1 : right_depth + 1; 
}

编辑于 2015-02-10 17:49:00 回复(0)

我是大牛膜拜吧小白

public Solution class{
   public int getHeight(TreeNode root){
         if(null==root)return 0;
         int m=getHeight(root.left);
         int n=getHeight(root.right);
         return m>n?m+1:n+1;
   }
}

编辑于 2017-02-25 23:13:45 回复(0)