二叉树的深度（剑指offer-38）

题目描述

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

递归解析：

思路：从根节点出发，查询左子树的深度，获取右子树的深度，比较一下，取大的，再加一。就是整个二叉树的深度。

递归的三个条件

边界条件：当前节点下，是否还有子节点，没有返回，有继续递归

递归前进段：当前节点下，还有子节点

递归返回段：当前节点下，没有子节点

递归解答

/**

public class TreeNode {

    int val = 0;

    TreeNode left = null;

    TreeNode right = null;

    public TreeNode(int val) {

        this.val = val;

    }

}

*/

public class Solution {

    public int TreeDepth(TreeNode root) {

        if(root==null)

            return 0;

        else

            return 1+Math.max(TreeDepth(root.left),TreeDepth(root.right));

    }

}

非递归解析（层次遍历）

经典的非递归层次遍历：利用辅助队列，先将头节点入队列，当队列不空时出队列的节点记为current，

当current左节点不空时入队列，其右节点不空时入队列，如此循环即可。

求深度：构造变量cur记录当前层访问到的节点数，width记录当前层的总个数，每当访问过一层层数deep++；

此种方法同时可以求最大宽度，访问第几层的第几个节点，是一种通用方法！

import java.util.LinkedList;

import java.util.Queue;

public class Solution {

    public int TreeDepth(TreeNode root) {

        if(root==null) return 0;

        TreeNode current;  //记录当前节点

        Queue<TreeNode> queue = new LinkedList<TreeNode>();  //构造辅助队列

        int cur,width;           //cur记录访问到当前层的第几个,width为当前层的宽度

        int deep=0;            //初始深度为0；

        queue.offer(root);          //头结点入队列

        while(!queue.isEmpty()){        //队列不空 循环记录深度

            cur=0;                                //新的一层cur赋为0

            width=queue.size();           //当前队列里的节点即为该层的所有节点

            while(cur<width){               //循环访问该层的所有节点

                current=queue.poll();    //访问队列的头

                if(current.left!=null)       //左节点不空，左节点入队列

                    queue.offer(current.left);

                if(current.right!=null)     //右节点不空，右节点入队列

                    queue.offer(current.right);

                cur++;           //访问完当前节点后cur++

            }

            deep++;            //访问完一层，层数++;

        }

        return deep;

    }

}

巴特西

二叉树的深度（剑指offer-38）

题目描述

递归解析：

递归解答

非递归解析（层次遍历）

最新文章

热门文章