剑指Offer-二叉树的深度-蒲公英云

剑指Offer-二叉树的深度

题目描述

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

解题思路—使用堆栈：使用堆栈依次压入路径，当路径达到叶结点时，计算堆栈长度，再弹出结点，计算另外路径的长度。最后比较得出长度最大值，即树的最大深度。
解题思路—递归：这段代码体现出了递归的精髓，特别简洁，但是不太易懂。从根结点一直递归到叶结点，从叶节点开始往上计算深度，每弹出一个子结点就深度+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;
    }
}