剑指Offer-二叉树的深度

布满荆棘的人生 2022-02-19 07:06 183阅读 0赞

## 题目描述 ##

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

解题思路—**使用堆栈**：**使用堆栈依次压入路径，当路径达到叶结点时，计算堆栈长度，再弹出结点**，计算另外路径的长度。最后比较得出长度最大值，即树的最大深度。  
解题思路—**递归**：这段代码**体现出了递归的精髓**，特别简洁，但是不太易懂。**从根结点一直递归到叶结点，从叶节点开始往上计算深度**，每弹出一个子结点就深度+1，同时与兄弟子树深度相比，取最大值作为当前根结点的深度。**注：** 代码可以简洁到一行，如果不太理解，可以拆分下来，进行debug。**推荐！**  
解题思路—**层次遍历**：层次遍历就是**一层一层的压入树的结点**，可以使用**队列**来存储。每次深度+1，就压入一层树结点，直至没有结点可以压入，则当前深度就是最大深度。

## Java解题—使用堆栈 ##

import java.util.Stack;
    public class Solution {
        public int count = 0;
        public int TreeDepth(TreeNode root) {
            if(root==null)
                return 0;
            Stack<TreeNode> stack = new Stack<>();
            CalNode(stack, root);
            return count;
        }
        
        public void CalNode(Stack<TreeNode> stack, TreeNode root){
            if(root!=null) {
                stack.push(root);
                if(root.left==null && root.right==null){
                    int num = stack.size();
                    count = num > count ? num : count;;
                    stack.pop();
                    return;
                }
                if(root.left!=null) CalNode(stack, root.left);
                if(root.right!=null) CalNode(stack, root.right);
                stack.pop();
            }
        }
    }

## Java解题—递归 ##

public class Solution {
        public int TreeDepth(TreeNode root) {
            if(root==null)
                return 0;
            return Math.max(TreeDepth(root.left), TreeDepth(root.right))+1;
            
            // 代码一行看不懂可以分接下来debug
    //        int left = TreeDepth(root.left);
    //        int right = TreeDepth(root.right);
    //        int count = Math.max(left, right) + 1;
    //        return count;
        }
    }

## Java解题—层次遍历 ##

import java.util.Queue;
    import java.util.LinkedList;
    public class Solution {
        public int TreeDepth(TreeNode root) {
            if(root==null)
                return 0;
    
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.add(root);
            int count = 0;
            while(!queue.isEmpty()){
                count++;
                // 将同一层的全部弹出
                int size = queue.size();
                for(int i=0;i<size;i++){
                    TreeNode node = queue.poll();
                    if(node.left!=null)
                        queue.add(node.left);
                    if(node.right!=null)
                        queue.add(node.right);
                }
            }
            return count;
        }
    }