資料結構-二叉樹（計算二叉樹深度的遞歸與非遞歸算法）

思路

二叉樹深度遞歸怎麼去想問題？

求二叉樹的深度為什麼可以用遞歸呢？這是因為我們這樣思考問題：求一個二叉樹的深度，我們即求根結點所在二叉樹的深度，即求左右子樹的最大深度，對于每個結點都是求左右子樹的最大深度，這樣就是把一個大的問題切分成小的問題，然後最小的問題有一個出口，結點為空時深度為 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;
    }