Java 資料結構進階二元樹題集上

2022-04-02 10:01:31

1、二元樹的遍歷

（1）前、中、後序遍歷

這裡寫到的遍歷是遞迴遍歷，程式碼比較簡單，後續會寫非遞迴的程式碼。以前序遍歷為例：

如果根節點root為空，直接返回，否則，列印根節點，再分別遞迴root的左子樹和右子樹即可。中序遍歷的話，先中序遍歷左子樹，列印根節點，再中序遍歷右子樹即可。

【程式碼如下】

//遞迴實現，比較簡單
public void preTree(Node root){
        if(root==null){
            return;
        }
        System.out.print(root.val+" ");
        preTree(root.left);
        preTree(root.right);
    }

（2）層序遍歷

【OJ連結】

OJ的返回值為一個存放連結串列的連結串列，所以我們可以將每一層的元素存放在同一個連結串列中，作為元素存放在要返回的連結串列中。還是使用佇列來遍歷連結串列，每次出根節點，當其左右節點不為空的時候，入左右節點。直到佇列為空，遍歷完成。

如何判斷二元樹每層結點的個數？

在對每層節點出隊完成後，佇列中剩餘結點的個數就是下一層結點的個數。比如：現在給佇列如跟節點，佇列大小為1，第一層的節點個數就為1；當根節點出對後，我們需要入隊根節點的左右節點，如果左節點為null，則只入右節點，此時佇列大小為1，第二層的節點個數就為1。

【程式碼如下】

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret=new ArrayList<>();
        if(root==null){
            return ret;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> list=new ArrayList<>();
            int size=queue.size();
            while(size--!=0){
                TreeNode node=queue.poll();
                list.add(node.val);
                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
            }
            ret.add(list);
        }
        return ret;
    }

2、獲取樹中子結點的個數

通常二元樹的問題，都會有兩種思路：遍歷思路和子問題思路。

如這道題：

我們可以求出它的左子樹和右子樹中子結點的個數，相加即可；或者，定義計數器，因為要遞迴，所以我們需要一個全域性變數（count），遞迴左右子樹，只要遇到子節點，count就加一。

【程式碼如下】

//獲取葉子節點的個數
    //方法一
    public int getLeafNodeCount1(Node root){
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }
        return getLeafNodeCount1(root.left)+getLeafNodeCount1(root.right);
    }
    // 方法二
    public static int count1;
    public void getLeafNodeCount2(Node root){
        if(root==null){
            return ;
        }
        if(root.left==null&&root.right==null){
            count1++;
        }
        getLeafNodeCount2(root.left);
        getLeafNodeCount2(root.right);
    }

3、獲取二元樹的高度

獲取二元樹的高度，我們只需要獲取二元樹左右子樹的高度，返回左右子樹的最大高度加一即可。

【程式碼如下】

 // 獲取二元樹的高度
    public int getHeight(Node root){
        if(root==null){
            return 0;
        }
        int left=getHeight(root.left);
        int right=getHeight(root.right);
        return left>right?left+1:right+1;
    }

4、判斷是不是完全二元樹

【完全二元樹和滿二元樹】

滿二元樹: 一棵二元樹，如果每層的結點數都達到最大值，則這棵二元樹就是滿二元樹。也就是說，如果一棵二元樹的層數為K，且結點總數是 2^K-1，則它就是滿二元樹。
完全二元樹: 完全二元樹是效率很高的資料結構，完全二元樹是由滿二元樹而引出來的。對於深度為K的，有n個結點的二元樹，當且僅當其每一個結點都與深度為K的滿二元樹中編號從0至n-1的結點一一對應時稱之為完全二元樹。要注意的是滿二元樹是一種特殊的完全二元樹。

判斷完全二元樹，我們可以藉助佇列來實現，在二元樹不為空的情況下，對二元樹進行層序遍歷：定義一個佇列，將根節點放入，只要佇列不為空，進行出隊，將得到的節點的左右節點入隊，注意先左後右，節點為空也要進行入隊（佇列可以儲存null）。直到遇到第一個出隊的節點為null，對佇列中剩下的元素進行遍歷，如果全為null，則為完全二元樹；如果存在不為null的結點，則不是完全二元樹。

 public boolean isCompleteTree(Node root){
       Queue<Node> queue=new LinkedList<>();
       queue.offer(root);
       //如果佇列為空，會存在空指標異常
       while(!queue.isEmpty()){
           //層序遍歷
           Node node=queue.poll();
           if(node!=null){
               //將節點的左右子節點放入佇列
               queue.offer(node.left);
               queue.offer(node.right);
           }else{
               //如果node為null，直接對佇列進行判斷
               break;
           }
       }
       int x=queue.size();
       //判斷佇列元素是否全為null
       for(int i=0;i<x;++i){
           if(queue.poll()!=null){
               return false;
           }
       }
       return true;
    }

5、判斷兩個樹是否相同

【OJ連結】

存在以下四種情況：

【程式碼如下】

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);
    }
}

6、另一棵樹的子樹

【OJ連結】

上面已經給寫過判斷兩棵樹是否相等的題，我們只需要判斷樹p是否等於樹q，或者數p的左子樹或右子樹是否等於樹q。分為以下幾種情況：

【程式碼如下】

class Solution {
    //判斷兩個樹是否相等
    public boolean isSameTree(TreeNode root,TreeNode subRoot){
        if(root==null&&subRoot!=null||root!=null&&subRoot==null){
            return false;
        }
        if(root==null&&subRoot==null){
            return true;
        }
        if(root.val!=subRoot.val){
            return false;
        }
        return isSameTree(root.left,subRoot.left)&&isSameTree(root.right,subRoot.right);
    }
    //判斷子樹
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root==null||subRoot==null){
             return false;
        }
        if(isSameTree(root,subRoot)){
            return true;
        }
        return isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot);
    }
}

7、判斷平衡二元樹

【OJ連結】

高度平衡二元樹定義為：

一個二元樹每個節點的左右兩個子樹的高度差的絕對值不超過 1 。

首先我們需要寫一個函數來求二元樹的高度，只要這個二元樹的左右子樹高度差不大於1，且左右子樹都是平衡二元樹，則其為平衡二元樹。

【程式碼如下】

class Solution {
    //求二元樹的高度
    public int maxDepth(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=maxDepth(root.left);
        int right=maxDepth(root.right);
        return left>right?left+1:right+1;
    }
    //判斷二元樹是不是平衡二元樹
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        if(Math.abs(maxDepth(root.left)-maxDepth(root.right))<=1){
            return isBalanced(root.left)&&isBalanced(root.right);
        }
        return false;
    }
}

到此這篇關於Java 資料結構進階二元樹題集上的文章就介紹到這了,更多相關Java 二元樹內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！

Java 資料結構進階二元樹題集上

目錄

1、二元樹的遍歷

（1）前、中、後序遍歷

（2）層序遍歷

2、獲取樹中子結點的個數

3、獲取二元樹的高度

4、判斷是不是完全二元樹

5、判斷兩個樹是否相同

6、另一棵樹的子樹

7、判斷平衡二元樹

熱門文章