算法：计算二叉树的高度

Java 实现

public class TreeHeight {

    public static void main(String[] args) {
        TreeHeight tree = new TreeHeight();
        Node node1 = new Node(3);
        Node node2 = new Node(9);
        Node node3 = new Node(20);
        Node node4 = new Node(15);
        Node node5 = new Node(7);
        /*tree.add(node1);
        tree.add(node2);
        tree.add(node3);
        tree.add(node4);
        tree.add(node5);*/
//        System.out.println(tree.root.id);
//        System.out.println(tree.height(tree.root));

        tree.root = node1;
        node1.left = node2;
        node1.right = node3;
        node3.left = node4;
        node3.right = node5;

        System.out.println(tree.height(tree.root));
    }

    public Node root;

    public int height(Node node) {
        if (node == null) {
            return 0;
        }
        int leftHeight = height(node.left);
        int rightHeight = height(node.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }

    public void add(Node node) {
        root = add(root, node);
    }

    private Node add(Node root, Node node) {
        if (root == null) {
            return node;
        }
        if (root.id > node.id) {
            root.left = add(root.left, node);
        } else {
            root.right = add(root.right, node);
        }
        return root;
    }

    private static class Node {
        public int id;
        public Node left;
        public Node right;

        public Node(int id) {
            this.id = id;
        }
    }

}

Golang 实现

定义树和节点

type AVLTree struct {
    root *AVLNode
}

type AVLNode struct {
    id    int
    left  *AVLNode
    right *AVLNode
}

当前节点的高度

递归结算，并注意自身节点高度为1，递归一次累加1。

// Height 以当前节点为根节点的树的高度
func (node *AVLNode) Height() int {
    var leftHeight int
    if node.left == nil {
        leftHeight = 0
    } else {
        leftHeight = node.left.Height()
    }

    var rightHeight int
    if node.right == nil {
        rightHeight = 0
    } else {
        rightHeight = node.right.Height()
    }

    if leftHeight > rightHeight {
        return leftHeight + 1
    } else {
        return rightHeight + 1
    }
}

当前节点左子树的高度

func (node *AVLNode) leftHeight() int {
    if node.left == nil {
        return 0
    }
    return node.left.Height()
}

当前节点右子树的高度

func (node *AVLNode) rightHeight() int {
    if node.right == nil {
        return 0
    }
    return node.right.Height()
}

树的高度

func (tree *AVLTree) Height() int {
    return tree.root.Height()
}

树的左子树高度

func (tree *AVLTree) leftHeight() int {
    if tree.root.left == nil {
        return 0
    }
    return tree.root.leftHeight()
}

树的右子树高度

func (tree *AVLTree) rightHeight() int {
    if tree.root.right == nil {
        return 0
    }
    return tree.root.rightHeight()
}