数据结构-二叉树（计算二叉树深度的递归与非递归算法）

思路

二叉树深度递归怎么去想问题？

求二叉树的深度为什么可以用递归呢？这是因为我们这样思考问题：求一个二叉树的深度，我们即求根结点所在二叉树的深度，即求左右子树的最大深度，对于每个结点都是求左右子树的最大深度，这样就是把一个大的问题切分成小的问题，然后最小的问题有一个出口，结点为空时深度为 0

Java 实现

// 结点
class Node {
    int data;
    Node left = null;
    Node right = null;
}

// 二叉树
public class BinaryTree {
    // 根结点
    private Node root;
    // 输入的数组
    private int[] arr_in;
    // 输出的数组
    private int[] arr_out;
    // 记录数组下标
    private static int index;
    
    // 初始化
    public BinaryTree(int[] arr) {
        root = new Node();
        this.arr_in = arr;
        arr_out = new int[arr.length];
        index = 0;
    }

	// 二叉树深度（递归）
    public int getDepthRecursion(Node r) {
        if (r != null) {
            int m = getDepthRecursion(r.left);
            int n = getDepthRecursion(r.right);
            return (m>=n)?(m+1):(n+1);
        }
        else
            return 0;
    }
    
    // 二叉树深度（非递归）
    public int getDepth(Node r) {
        Stack stack = new Stack();
        Node node = r;
        Node top;
        int depth = 0;
        int maxDepth = 0;
        while(node || !stack.empty()) {
            if (node != null) {
                stack.push(node);
                depth++;
                if (depth > maxDepth)
                    maxDepth = depth;
                node = node.left;
            }
            else {
                if (stack.peek().right && stack.peek().right != top)
                    node = stack.peek().right();
                else {
                    top = stack.pop();
                    depth--;
                    node = null;
                }
            }
        }
        return maxDepth;
    }