剑指Offer: 二叉树的深度

本是古典何须时尚 2023-07-18 14:14 22阅读 0赞

##### 1. 题目描述 #####

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。  
原题传送门：[link][].

##### 2. 提取关键词 #####

二叉树深度

##### 3. 思路 #####

*  见注释

##### 4. 代码（Java） #####

/**
    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;
            } 
            //统计左节点的数
            int LD=TreeDepth(root.left);
            //统计左节点的数
            int RD=TreeDepth(root.right);
            //到底端时h=1,每退出一层就返回对比左右子树最大深度并加1，最后返回的值就是最大的深度
            return (LD>RD?LD:RD)+1;
        }
    }
    //非递归
    import java.util.Queue;
    import java.util.LinkedList;
     
    public class Solution {
        public int TreeDepth(TreeNode pRoot)
        {
            if(pRoot == null){
                return 0;
            }
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.add(pRoot);
            int depth = 0, count = 0, nextCount = 1;//出栈时count记录出栈结点数，记录nextCount记录本层结点数
            while(queue.size()!=0){
                TreeNode top = queue.poll();
                count++;
                if(top.left != null){
                    queue.add(top.left);
                }
                if(top.right != null){
                    queue.add(top.right);
                }
                if(count == nextCount){
                    nextCount = queue.size();
                    count = 0;
                    depth++;
                }
            }
            return depth;
        }
    }

##### 5.复杂度 #####

*  暂无

##### 6. 知识积累 #####

*  暂无

[link]: https://www.nowcoder.com/practice/435fb86331474282a3499955f0a41e8b?tpId=13&tqId=11191&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking