【剑指offer-Java版】39二叉树的深度

r囧r小猫 2022-08-21 10:45 136阅读 0赞

二叉树的深度：递归

判断二叉树是否是平衡二叉树:注意二叉树平衡代表的是所有非叶子节点都是一棵平衡树 – 而不仅仅是根节点

public class _Q39<T> {
    
        public int TreeDepth(BinaryTreeNode<?> tree){
            if(tree == null) return 0;
    
            if(tree.leftChild == null && tree.rightChild == null) return 1;
    
            int left = TreeDepth(tree.leftChild);
            int right = TreeDepth(tree.rightChild);
    
            return (left > right ? left : right) + 1;
        }
    
    
        public boolean IsBalance(BinaryTreeNode<?> tree, int depth[]){
            if(tree == null) return true;
    
            int depthL[] = {
       0};
            int depthR[] = {
       0};
            // 相当于后序遍历
            if(IsBalance(tree.leftChild, depthL) && IsBalance(tree.rightChild, depthR)){
                int diff = depthL[0] - depthR[0];
                if(diff <= 1 && diff >= -1){
                    depth[0] = (depthL[0] > depthR[0] ? depthL[0] : depthR[0]) + 1;
                    return true;
                }
            }
    
            return false;
        } 
    
    
        }

测试代码：

public class _Q39Test extends TestCase {
        
    
        _Q39<?> treeJudge = new _Q39();
    
        public void test(){
            BinaryTreeNode<Integer> root = new BinaryTreeNode<>();
            BinaryTreeNode<Integer> node1 = new BinaryTreeNode<>();
            BinaryTreeNode<Integer> node2 = new BinaryTreeNode<>();
            BinaryTreeNode<Integer> node3 = new BinaryTreeNode<>();
            BinaryTreeNode<Integer> node4 = new BinaryTreeNode<>();
            BinaryTreeNode<Integer> node5 = new BinaryTreeNode<>();
            BinaryTreeNode<Integer> node6 = new BinaryTreeNode<>();
    
            root.value = 10;
            node1.value = 6;
            node2.value = 14;
            node3.value = 4;
            node4.value = 8;
            node5.value = 12;
            node6.value = 16;
    
            root.leftChild = node1;
            root.rightChild = node2;
            //root.rightChild = null;
            node1.leftChild = node3;
            node1.rightChild = node4;
            node2.leftChild = node5;
            node2.rightChild = node6;
    
            node3.leftChild = null; node3.rightChild = null;
            node4.leftChild = null; node4.rightChild = null;
            node5.leftChild = null; node5.rightChild = null;
            node6.leftChild = null; node6.rightChild = null;
    
            System.out.println(treeJudge.TreeDepth(root));
            int depth[] = {
       0};
            System.out.println(treeJudge.IsBalance(root, depth));
        }
        }