//递归方式求树的深度，TreeTrace类里面有两个变量，一个是depth，该值就是树的深度。另外一个是trace，
//是arrayLIst的集合,该集合就记录了树的旋转类型
//计算平衡因子只需要把getDepth（左子树的节点）的depth和getDepth右子树的depth相减即可。
public static Treetrace getDepth(SearchTreeNode currentNode) {

         if (currentNode == null){
            return new Treetrace();
        }

        Treetrace rightTrace = getDepth(currentNode.right);
        Treetrace leftTrace = getDepth(currentNode.left);
        if (rightTrace.depth>leftTrace.depth){
            rightTrace.depth++;
            if (currentNode.right != null || currentNode.left!=null){
                rightTrace.trace.add("right");
            }
            return rightTrace;
        }
        else {
            if (currentNode.right != null || currentNode.left!=null){
                leftTrace.trace.add("left");
            }
            leftTrace.depth++;
            return leftTrace;
        }
    }
}

class SearchTreeNode{
    SearchTreeNode parent ;
    SearchTreeNode left ;
    SearchTreeNode right ;
    int value;

    SearchTreeNode(int value){
        this.value = value;
        parent = null;
        right = null;
        left = null;
    }
}

class Treetrace{
    int depth=0;
    ArrayList<String> trace = new ArrayList<>();
}