Java-数构二叉树-EW帮帮网

1.树

1.1概念

树是一种非线性的数据结构，它是由n个有限节点组成一个具有层次关系。这种结构有以下特点：

一个特殊的结点，称为根节点，根节点没有前驱节点
除根节点以外，其余节点分成M个互不相交的集合。每个集合又是一颗和树类似的子树。每颗子树的根节点有且只有一个前驱，可以有0个或者多个后继。
树是递归定义的。

树形结构中，子树之间是不能有交集的，否则就不是树形结构。除了根节点以外，每一个节点有且只有一个父结点。

一棵树有N个节点就有N-1条边。

1.2概念

结点的度：一个结点含有子树的个数。
树的度：一棵树中，所有结点度最大值称之为树的度。
叶子结点或终端结点：度为0的结点称作叶子结点；
双亲结点或父结点：若一个结点含有子节点，则称这个结点为其子节点的父节点。
孩子结点或子结点：一个结点含有的子树的根节点乘坐该结点的子节点。
根结点：一棵树中，没有双亲结点的结点
结点的层次：从根开始定义，根为第一层，根的子结点为第2层
树的高度或深度：树中结点的最大层次
兄弟结点：具有相同父节点的结点互相称为兄弟结点
子孙：以某结点为根的子树中任一结点都称为该结点的子孙
森林：由m棵互不想接的树构成的集合称为森林

1.3树的表示形式

双亲表示法， 孩子表示法 、 孩子双亲表示法 、 孩子兄弟表示法 等等。我们这里就简单的了解其中最常用的 孩子兄弟表示法 。

2二叉树

2.1概念

一颗二叉树是结点的有限集合，该集合：或者为空，或者是由一个根节点加上两颗别称为左子树和右子树的二叉树构成。

注意：

二叉树不存在度大于2的结点
二叉树的子树有左右之分，次序不可颠倒，因此二叉树是有序树

2.2两种特殊的二叉树

满二叉树：一颗二叉树，如果每层的节点数都达到最大值，则这颗二叉树是满二叉树，也就是说如果有一颗二叉树的层数为K，且结点总数为 $2^k - 1$ ，则他是满二叉树。
完全二叉树：完全二叉树是一种效率很高的数据结构，完全二叉树是由满二叉树引申出来的。对于深度为K的，有n个结点的二叉树，当且仅当其中每一个结点都与深度为K的满二叉树中从0到n-1的结点对应时才为完全二叉树。

2.3二叉树的性质

若根节点的层数为1，则一颗非空二叉树的第i层上最多有 $2^{i-1} \quad (i > 0)$ 个结点
若只有根节点的二叉树的深度为1，则深度为K 的二叉树党的最大结点数为 $2^{k-1} \quad (k >= 0)$ 。
对于任何一棵二叉树，如果其叶节点个数为n0（度为0）,度为2的非叶结点的个数为n2，则有 $n0=n2+1$
具有n个结点的完全二叉树的深度k为 $\lfloor \log_2(n+1) \rfloor$ 向上取整
对于具有n个结点的完全二叉树，如果按照从上至下，从左至右的顺序对所有结点从0开始编号，则对于需要为i的结点有：

若i>0，双亲的序号为： $(i-1)/2$ ；若i=0，i为根节点编号，没有双亲结点
若2i+1<n，左孩子序号为 $2i+1$ ，否则没有左孩子
若2i+1>n，左孩子序号为 $2i+2$ ，否则没有右孩子

2.4二叉树的存储

存储结构分为：顺序存储和类似于链表形式的链式存储。二叉树的链式存储是通过一个一个的节点引用起来的，常见的表示方式有二叉和三叉表示方式，

2.5二叉树的基本操作

2.1二叉树的遍历

1.前中后序遍历

所谓遍历是指沿着某条搜索路线，因此对树种每个结点均做一次且仅做一次的访问。

NLR：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点--->根的左子树--->根的右子树。
LNR：中序遍历(Inorder Traversal)——根的左子树--->根节点--->根的右子树。
LRN：后序遍历(Postorder Traversal)——根的左子树--->根的右子树--->根节点。

2.层序遍历

设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左到右逐层访问树的结点的过程就是层序遍历。

2.5.二叉树的基本方法

//树种节点的个数
public void nodeSize(TreeNode root){
        if(root==null) return ;
        size++;
        nodeSize(root.left);
        nodeSize(root.right);
    }
    public int nodeSize2(TreeNode root){
        if(root==null) return 0;
        return nodeSize2(root.left)+nodeSize2(root.right)+1;
    }
// 子问题思路-求叶子结点个数
public int leafSize=0;

    public void getLeafNodeCount(TreeNode root){
        if(root==null)return ;
        if(root.left==null&root.right==null){
            leafSize++;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
    }
    
    //左数的叶子+右数的叶子
    public int getLeafNodeCount2(TreeNode root){
        if(root==null)return 0;
        if(root.left==null&&root.right==null){
            return 1;
        }
        return getLeafNodeCount2(root.left)+getLeafNodeCount2(root.right);
    }
//第K层结点的个数
    public int getKLevelNodeCount(TreeNode root,int k){
        if(root==null) return 0;
        if(k==1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)+
                getKLevelNodeCount(root.right,k-1);
    }
// 获取二叉树的高度
public int getHeight(TreeNode root){
        if(root==null) return 0;
        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);

        return (leftHeight>rightHeight? leftHeight+1:rightHeight+1);
    }
// 检测值为value的元素是否存在
 public boolean find(TreeNode root,char key){
        if(root==null)return false;
        if(root.val==key){
            return true;
        }
        boolean leftVal=find(root.left,key);
        if (leftVal==true){
            return true;
        }
        boolean rightVal=find(root.right,key);
        if(rightVal==true){
            return  true;
        }
        return  false;
    }
//层序遍历
public void levelOrder1(TreeNode root){//层序遍历
        if(root==null){return;}
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            System.out.println(cur.val+" ");
            if(cur.left!=null){
                queue.offer(cur.left);
            }
            if(cur.right!=null){
                queue.offer(cur.right);
            }
        }
    }
public List<List<TreeNode>> levelOrder2(TreeNode root){//层序遍历
        List<List<TreeNode>> ret=new ArrayList<>();
        if(root==null){return ret;}
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size= queue.size();//当前队列的大小
            List<TreeNode> tmp=new ArrayList<>();
            while (size!=0){
                TreeNode cur=queue.poll();
                tmp.add(cur);
                size--;
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
            }
          ret.add(tmp);
        }
        return  ret;
    }

2.5.3常见0j

判断一棵树是否是完全二叉树

// 判断一棵树是不是完全二叉树
public boolean isCompleteTree(TreeNode root){
        if(root==null) return false;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            if (cur!=null){
                queue.offer(root.left);
                queue.offer(root.right);
            }else {
                break;
            }
        }
        while (!queue.isEmpty()){
            TreeNode cur=queue.poll();
            if(cur==null){
                return false;
            }
        }
        return true;
    }

思路：先把当前节点放入队列中，再弹出元素判断是否为空节点，若不为空将该节点的左右节点再入队，一直到队列中都为空。再挨个弹出队列中所剩下的元素，遇到null就说明不是完全二叉树。若非空说明元素都是按序排列的。

100. 相同的树

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q!=null||p!=null&&q==null){
            return false;
        }
        if(p==null&&q==null){
            return true;
        }
        if(p.val!=q.val){
            return false;
        }
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
}

思路：定义两个节点位于两棵树，若一个节点为空一个不为空，说明不是相同的树。若两个节点都为空，说明是两颗空树，则相同。若两个节点的值不相同，则不相同。遍历两树的左子树和右子树，只有当左右子树都相同的时候才是相同的树。

572. 另一棵树的子树

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
       if(root==null){
        return false;
       } 
       if(isSameTree(root,subRoot)){
        return true;
       }
      return isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot);
    }
    private boolean isSameTree(TreeNode p,TreeNode q){
        if(p==null&&q!=null||p!=null&&q==null){
            return false;
        }
        if(p==null&&q==null){
            return true;
        }
        if(p.val!=q.val){
            return false;
        }
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
}

思路与相同树类似。只不过可能从根结点处开始相同，也有可能与左右子树中任意一棵子树相同。

226. 翻转二叉树

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null){return null;}
        TreeNode tmp=root.left;
        root.left=root.right;
        root.right=tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

110. 平衡二叉树

class Solution {
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }

    private int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        if (leftHeight == -1) {
            return -1; // 左子树不平衡
        }
        int rightHeight = getHeight(root.right);
        if (rightHeight == -1) {
            return -1; // 右子树不平衡
        }
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1; // 当前节点不平衡
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

思路：平衡二叉树的概念是：平衡二叉树是指该树所有节点的左右子树的高度相差不超过 1。基本思路与求树的高度相同，遍历左右子树计算子树的高度，比较高度并加1。但是这里为预防重复计算高度设置一个-1值说明该子树已经不平衡了。

101. 对称二叉树

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null){
            return true;
        }
        return isSymmetricChild(root.left,root.right);
    }
    public boolean isSymmetricChild(TreeNode p,TreeNode q){
        if(p==null&&q!=null||p!=null&&q==null){
            return false;
        }
        if(p==null&&q==null){
            return true;
        }
        if(p.val!=q.val){
            return false;
        }
        return isSymmetricChild(p.left,q.right)&&isSymmetricChild(p.right,q.left);
    }
}

思路：遍历左右子树，当p.left==q.right且p.right==q.left时才满足对称。

给定一个字符串生成一个二叉树

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。

    public static  int i = 0;

    public static TreeNode creatrTree(String str) {
        TreeNode root = null;

        if(str.charAt(i) != '#') {
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = creatrTree(str);
            root.right = creatrTree(str);
        }else {
            i++;
        }
        return root;
    }
}

思路：按照先序遍历的方式创建二叉树。

236. 二叉树的最近公共祖先

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null)return null;
        if(root==p||root==q){
            return root;
        }
        TreeNode left=lowestCommonAncestor(root.left,p,q);
        TreeNode right=lowestCommonAncestor(root.right,p,q);
        if(left!=null&&right!=null){
            return root;
        }else if(left==null){
            return right;
        }else{
            return left;
        }
    }
}

思路：p，q若分别位于左右子树上那么最近公共祖先一定是根节点。若一个位于左或右子树上，一个位于根节点，那么根节点就是最近公共祖先。

105. 从前序与中序遍历序列构造二叉树

class Solution {
    public int preindex=0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }
    private TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend){
        if(inbegin>inend){
            return null;
        }
        TreeNode root=new TreeNode(preorder[preindex]);
        int rootIndex=findIdex(inorder,inbegin, inend,preorder[preindex] );
        if(rootIndex==-1){
            return null;
        }
        preindex++;
        root.left=buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
        root.right=buildTreeChild(preorder,inorder,rootIndex+1,inend);
        return root;
    }
    private int findIdex(int[] inorder,int inbegin,int inend,int key){
        for(int i=inbegin;i<=inend;i++){
            if(inorder[i]==key){
                return i;
            }
        }
        return -1;
    }
}

思路：按照手动画树的思路，前序遍历第一个数就是根节点，而中序遍历以这个数分作左右两棵子树。那么遍历前序遍历数组，并在中序遍历数组中找到对应下标，构建根节点。同时按照中序遍历顺序先构建左子树再构建右边子树。在中序遍历数组定义一个数组开头和结尾。调用是改变结尾或者开头的位置，一直到开头下标大于结尾下标时，说明子树构建完成。

106. 从中序与后序遍历序列构造二叉树

class Solution {
   public int postIndex;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex=postorder.length-1;
         return buildTreeChild(postorder,inorder,0,inorder.length-1);
    }
    
     private TreeNode buildTreeChild(int[] postorder,int[] inorder,int inbegin,int inend){
        if(inbegin>inend){
            return null;
        }
        TreeNode root=new TreeNode(postorder[postIndex]);
        int rootIndex=findIdex(inorder,inbegin, inend,postorder[postIndex]);
        if(rootIndex==-1){
            return null;
        }
        postIndex--;
        root.right=buildTreeChild(postorder,inorder,rootIndex+1,inend);
        root.left=buildTreeChild(postorder,inorder,inbegin,rootIndex-1);
        
        return root;
    }
    private int findIdex(int[] inorder,int inbegin,int inend,int key){
        for(int i=inbegin;i<=inend;i++){
            if(inorder[i]==key){
                return i;
            }
        }
        return -1;
    }
    }

思路：与前中序遍历创建子树同理。后序遍历最后一个节点为根节点。且子树创建顺序应该是先右子树后左子树。

606. 根据二叉树创建字符串

class Solution {
    public String tree2str(TreeNode root) {
        StringBuilder stringBuider=new StringBuilder();
        tree2strChild(root,stringBuider);
        return stringBuider.toString();
    }
    private void tree2strChild(TreeNode t,StringBuilder stringBuider){
        if(t==null){
            return;
        }
        stringBuider.append(t.val);
        if(t.left!=null){
            stringBuider.append("(");
            tree2strChild(t.left,stringBuider);
            stringBuider.append(")");

        }else{
            if(t.right==null){
                return ;
            }else{
                stringBuider.append("()");
            }
        }
        if(t.right!=null){
            stringBuider.append("(");
            tree2strChild(t.right,stringBuider);
            stringBuider.append(")");
        }else{
            return ;
        }
    }
}

思路：左子树不为空的时候添加左括号，在添加字符后添加右括号。若右子树节点为空那么添加左右括号。可以将情况分为：1左边不为空（右边为空，右边不为空）2.左边为空（右边为空，右边不为空)3.右边空4.右边不为空。

145. 二叉树的后序遍历

（非递归遍历）

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res=new ArrayList<Integer>();

        if(root==null) return res;
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        TreeNode top=null;
        TreeNode prev=null;
        
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
            stack.push(cur);
            cur=cur.left;
        }
        top=stack.peek();
        if(top.right==null||top.right==prev){
            stack.pop();
            res.add(top.val);
            prev=top;//当前结点被打印过了
        }else{
            cur=top.right;
        }
        } 
        return res;
    }
}

Java-数构二叉树

1.树