二叉树的子结构、深度以及重建二叉树

目录

  • 二叉树的深度
  • 平衡二叉树
  • 二叉树的子结构
  • 二叉树的重修
  • 总结
  • 参考资料

二叉树相关的套路,除了四种遍历方式,另有许多的内容,有二叉树的深度,将一个数组构建成为一个二叉树。
今天接着搞定二叉树。

二叉树的深度

剑指offer第55-I题,Leetcode第104题:

输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经由的节点(含根、叶节点)形成树的一条路径,
最长路径的长度为树的深度。

例如:给定二叉树[3,9,20,null,null,15,7],返会他的最大深度。

    3
   / \
  9  20
    /  \
   15   7

二叉树的深度,说白了就是二叉树有几层,因此可以使用层序遍历,统计有若干层即可:

使用层序遍历的方式:

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> queue=new LinkedList<>();
    queue.add(root);
    TreeNode node;
    int dep=1;
    while (!queue.isEmpty()){
        int len=queue.size();
        for (int i=0;i<len;i++){
            node=queue.remove();
            if(node.left!=null){
                queue.add(node.left);
            }
            if(node.right!=null){
                queue.add(node.right);
            }
        }
        dep++;
    }
    return dep;
}
  • 时间复杂度:将整个树每个节点访问了双方即O(n)
  • 空间复杂度:分外使用了一个栈来保留状态O(n)

除了层序遍历,思量递归的方式,对于根节点,划分求出左子树的深度和右子树的深度,取他们的最大值,
然后+1即是这棵树的深度。而左子树右子树同样,则有递归的方式如下:

public int maxDepth(ThreeNode root){
    //代表已经出树的结构
    if(root==null) return 0;
    return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
}

时间复杂度:遍历了所有的树的节点,O(n)
空间复杂度:当树退化成单链,则递归的深度为n,因此空间复杂度O(n)

平衡二叉树

平衡二叉树界说:若是某二叉树中随便节点的左右子树的深度相差不跨越1,那么它就是一棵平衡二叉树。

剑指offer第55-II题,Leetcode第110题:

输入一棵二叉树的根节点,判断该树是不是平衡二叉树。

平衡二叉树的观点讲的很清晰,要求随便一节点的左右子树的深度差不能跨越1,那么划分求出每个子树的
左右子树的深度,求差即可判断:

public boolean isBalanced(TreeNode root){
    if(root==null) return true;
    //划分判断左子树和右子树是不是平衡树,然后判断整棵树是不是平衡树
    return isBalanced(root.left)&&isBalanced(root.right)&&(Math.abs(maxDepth(root.left)-maxDepth(root.right))<2);
}

上面代码盘算判断每一个节点最先的二叉树都市判断他的所有子树是不是平衡二叉树,举行了大量的重复盘算,那若何省去这些重复的盘算呢?

谜底是从叶结点最先盘算,判断每一个叶结点为根的子树,是平衡树则返回他的树高,若是不是则返回-1,然后对其父父节点为根的子树,使用返回的树高举行盘算。

阿里P7岗位面试,面试官问我:为什么HashMap底层树化标准的元素个数是8

    public boolean isBalanced2(TreeNode root){
        return recur(root)!=-1;
    }

    public int recur(TreeNode root){
        if (root==null) return 0;
        int left=recur(root.left);
        if(left==-1) return -1;
        int right=recur(root.right);
        if(right==-1) return -1;
        return Math.abs(left-right)>1?-1:Math.max(left,right)+1;
    }

二叉树的子结构

剑指offer第26题:

输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是随便一个树的子结构),B是A的子结构, 即 A中有泛起和B相同的结构和节点值。

例如:

给定的树 A:

     3
    / \
   4   5
  / \
 1   2
给定的树 B:
   4 
  /
 1

返回 true,由于 B 与 A 的一个子树拥有相同的结构和节点值。

这个题我第一反映,要用A树种的每一个节点作为A的某棵子树的根节点和B举行对照。
以是我以为需要用个行列或者栈或者列表将遍历整个树获得的元素保留起来,再逐一判断。
然则我已经遍历乐一遍了,在遍历的时刻遍历到当前节点就对以当前节点为根的子树举行判断,不好吗?

public boolean isSubStructure(TreeNode A, TreeNode B){
    if(A==null || B==null) return false;
    return help(A,B)||isSubStructure(A.left,B)||isSubStructure(A.right,B);
}

//从A的根和B的跟最先判断是不是一样的结构
//这句话不知道怎么形貌
public boolean help(TreeNode A, TreeNode B){
    if(B==null) reurn false;
    if(A==null || A.val!=B.val) return false;
    return help(A.left,B.left)&&help(A.right,B.right);
}

二叉树的重修

二叉树的重修,嗯。。。想起来挺简朴,做起来挺不简朴的。。。

剑指offer第7题,Leetcode第105题:

输入某二叉树的前序遍历和中序遍历的效果,请重修该二叉树。假设输入的前序遍历和中序遍历的效果中都不含重复的数字。

例如:

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下二叉树

    3
   / \
  9  20
    /  \
   15   7

怎么说,刚看到这个问题一脸茫然,似乎大学学过,然则呢,,,嗯学的惨不忍睹。。。

  • 首先:二叉树不管前序,中序照样后序遍历,获得的元素的个数,一定是一样的
  • 其次:前序遍历的第一个节点一定是整个树的根
  • 第三:中序遍历中,排在根节点前面的一定是左子树的节点,后面的一定是右子树的节点
  • 第四:若是根节点存在左子树,那么前序遍历中,根节点后面跟的一定是左子树的值,数目和中序遍历中左子树的个数一样
  • 最后,另有一句保证内里没有重复元向来保证我们在中序遍历中查找根节点的时刻是唯一的。

至此,可以将中序便利的数组分为三部门,根节点,左子树和右子树,对于左右子树,他们又是一个完成的树结构,重复以上方式即可。

什么意思呢?对于上面的问题:

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

凭据前序遍历可以获得根节点是3 
将中序遍历的效果分为3部门 左子树[9],根节点[3],右子树[15,20,7]
        3
       / \
      9  [15,20,7]

在前序遍历中对应的[15,20,7]的遍历效果是[20,15,7]
重复上述历程则有

    3
   / \
  9  20
    /  \
   15   7

上代码:

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if(preorder==null||preorder.size()==0) return null;
    int len=preorder.size();
    Map<Integer,Integer> indexMap=new HashMap<>();
    for(int i=0;i<len;i++){
        indexMap.put(inorder[i],i);
    }
    
}

public TreeNode buildTree(int[] preorder, int preStrat,int preEnd,
                          int[] inorder, int inStart, int inEnd,
                          Map<Integer,Integer> indexMap){
    if(preStart>preend) return null;
    int rootVal=preorder[preStart];
    TreeNode root =new TreeNode(rootVal);
    int rootIndex=indexMap.get(rootVal);
    int leftNodes=rootIndex-instart;
    int rigthNodes=inEnd-rootIndex;
    root.left=buildTree(preorder,preStrat+1,preStrat+leftNodes,
                        inorder,inStart,rootIndex-1,
                        indexMap);
    root.right=buildTree(preorder,preEnd-rightNodes+1,preEnd,
                         inorder,rootIndex+1,inEnd,
                         indexMap);
    return root;
    
}

总结

对于树的种种操作分治头脑是一个很巧妙的头脑,要判断一整棵树,可以先判断左右子树,依次递归,注重递归退出的边界条件。

参考资料

  • leetcode对应题号以及剖析

原创文章,作者:2d28新闻网,如若转载,请注明出处:https://www.2d28.com/archives/21081.html