【植树节】程序员们一起来种“二叉树”啦

vlambda
2021-03-13

【植树节】程序员们一起来种“二叉树”啦

天眼创智

让每一个人品质就业不再难

3月12日又是一年植树节

科技改变视界版图

代码创造绿色动力

勤勤恳恳的“码农”们

也开始响应绿色环保的号召

一起来种“二叉树”啦

”

Binary tree/ 二叉树

数组、栈、队列、链表都是线性结构，树则是另外一种极其重要的数据结构。

树的种类有很多种，我们先从二叉树入手，总结求职面试必考二叉树高频试题。

”

· 二叉树的基本数据结构：

class TreeNode{
int val;
//左孩子
TreeNode left;
//右孩子
TreeNode right;

}

· 二叉树的最大深度：

int maxDeath(TreeNode node){
if(node==null){
return 0;
    }
    int left = maxDeath(node.left);
    int right = maxDeath(node.right);
    return Math.max(left,right) + 1;
}

· 二叉树的最小深度：

int getMinDepth(TreeNode root){
        if(root == null){
            return 0;
        }
        return getMin(root);
    }
    int getMin(TreeNode root){
        if(root == null){
            return Integer.MAX_VALUE;
        }
        if(root.left == null&&root.right == null){
            return 1;
        }
        return Math.min(getMin(root.left),getMin(root.right)) + 1;
    }

· 二叉树中的节点个数：

int maxDeath(TreeNode node){
if(node==null){
return 0;
    }
    int left = maxDeath(node.left);
    int right = maxDeath(node.right);
    return Math.max(left,right) + 1;
}

· 二叉树是否为平衡二叉树：

boolean isBalanced(TreeNode node){
        return maxDeath2(node)!=-1;
    }
    int maxDeath2(TreeNode node){
        if(node == null){
            return 0;
        }
        int left = maxDeath2(node.left);
        int right = maxDeath2(node.right);
if(left==-1||right==-1||Math.abs(left-right)>1) {

            return -1;
        }
        return Math.max(left, right) + 1;
    }

· 判断二叉树是否是完全二叉树：

boolean isCompleteTreeNode(TreeNode root){
        if(root == null){
            return false;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        boolean result = true;
        boolean hasNoChild = false;
        while(!queue.isEmpty()){
            TreeNode current = queue.remove();
            if(hasNoChild){
if(current.left!=null||current.right!=null){
                    result = false;
                    break;
}
            }else{
                if(current.left!=null&&current.right!=null){
                    queue.add(current.left);
                    queue.add(current.right);
                }else if(current.left!=null&&current.right==null){
                    queue.add(current.left);
                    hasNoChild = true;
                }else if(current.left==null&&current.right!=null){
                    result = false;
                    break;
                }else{
                    hasNoChild = true;
                }
            }
        }
        return result;
    }

· 两个二叉树是否完全相同：

boolean isSameTreeNode(TreeNode t1,TreeNode t2) {
        if(t1==null&&t2==null){
            return true;
        }
        else if(t1==null||t2==null){
            return false;
        }
        if(t1.val != t2.val){
            return false;
        }
        boolean left = isSameTreeNode(t1.left,t2.left);
        boolean right = isSameTreeNode(t1.right,t2.rig ht);
        return left&&right;
    }

· 两个二叉树是否互为镜像：

boolean isMirror(TreeNode t1,TreeNode t2){
if(t1==null&&t2==null){
return true;
}
if(t1==null||t2==null){
return false;
}
if(t1.val != t2.val){
return false;
}
return isMirror(t1.left,t2.right)&&isMirror(t1.right,t2.left);
}