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

2022-04-02 10:01:30

1、對稱二元樹

分為以下幾種情況：

二元樹為空，是對稱二元樹
二元樹不為空，其左子樹或者右子樹為空，不是對稱二元樹
二元樹不為空，左右子樹都為空，是對稱二元樹
二元樹不為空，左右子樹不為空，左右子節點值不同，不是對稱二元樹
二元樹不為空，左右子樹不為空，左右子節點值相同，如果左子樹的左節點和右子樹的右節點、左子樹的右節點和右子樹的左節點相同，則其為對稱二元樹，否則，不是對稱二元樹。

【程式碼如下】

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

2、建立並遍歷二元樹

【OJ連結】

【題目描述】

讀入使用者輸入的一串先序遍歷字串，根據此字串建立一個二元樹（以指標方式儲存）。例如如下的先序遍歷字串： ABC##DE#G##F### 其中“#”表示的是空格，空格字元代表空樹。建立起此二元樹以後，再對二元樹進行中序遍歷，輸出遍歷結果。

關於這個題，完全從零開始，我們需要定義（1）二元樹的節點，（2）中序遍歷的函數，（3）根據先序遍歷字串建立二元樹的函數，（4）主函數。建立節點、中序遍歷、主函數不用多說。主要說一下根據先序遍歷字串來建立二元樹的過程：

遍歷字串，#表示空，就分為以下兩種情況：如果字元不為空，我們需要建立根節點，然後遞迴建立其的左右子樹；否則，直接跳過即可。

【程式碼如下】

import java.util.Scanner;
    //定義二元樹的節點
    class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;
        public  TreeNode(char val){
            this.val=val;
        }
    }
public class Main {
    //根據先序遍歷字串建立二元樹
    public static int i=0;
    public static TreeNode createTree(String s){
        TreeNode root=null;
        //字元不為空的情況下，建立根節點
        if(s.charAt(i)!='#'){
            root=new TreeNode(s.charAt(i));
            i++;
            //遞迴建立root的左右子樹
            root.left=createTree(s);
            root.right=createTree(s);
        }else{
            //字元為空，直接跳過
            i++;
        }
        return root;
    }
    public static void inorderTree(TreeNode root){
        if(root==null){
            return;
        }
        inorderTree(root.left);
        System.out.print(root.val+" ");
        inorderTree(root.right);
    }
    //中序遍歷二元樹
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()){ 
            String s=in.nextLine();
            TreeNode node=createTree(s);
            inorderTree(node);
        }
    }
}

3、二元樹中兩節點最近公共祖先

【OJ連結】

二元樹的根節點為root，以及兩個節點p、q，如果二元樹為空，則返回null；如果二元樹的根節點等於p或者q，或者p、q在根節點的左右兩側，則其最近公共結點為root；如果p、q系欸但在root節點的同側，則最小公共結點就是該側的節點。

【程式碼如下】

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

4、二元搜尋樹與雙向連結串列

【OJ連結】

二元搜尋樹：任何節點的左子樹小於右子樹

將二元搜尋樹轉換為有序的雙向連結串列：

二元搜尋樹的中序遍歷結果為有序的。所以我們只需要寫一箇中序遍歷，在其中實現其節點左右指向的改變即可。首先我們需要一個前驅節點prev來儲存每個節點的左節點，初始為null，因為是雙向連結串列，所以prev還需要指向它的右節點，如果其為空，則不用。

【程式碼如下】

public class Solution {
    public TreeNode prev=null;
    //中序遍歷二元樹
    public void inorderTree(TreeNode root){
        if(root==null){
            return ;
        }
        inorderTree(root.left);
        //處理二元樹的左右節點
        root.left=prev;
        if(prev!=null){
            prev.right=root;
        }
        prev=root;
        inorderTree(root.right);
    }
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null){
            return null;
        }
        inorderTree(pRootOfTree);
        while(pRootOfTree.left!=null){
            pRootOfTree=pRootOfTree.left;
        }
        return pRootOfTree;
    }
}

5、根據前序和中序遍歷結果建立二元樹

【OJ連結】

給出一個二元樹的前序遍歷和中序遍歷的結果，根據其建立二元樹：

我們知道，前序遍歷的第一個元素（prev）一定是根節點（從前往後遍歷），所以在中序遍歷中找到prev，則左邊元素為左子樹元素，右邊元素為右子樹，建立根節點，遞迴建立左子樹和右子樹。注意一定要先建立左子樹，因為先序遍歷的因素，先序遍歷陣列的下一個元素一定是左子樹的根節點。【如果是根據後序遍歷和中序遍歷建立二元樹，則後序遍歷的陣列需要從後往前遍歷，還有，一定要先遞迴建立右子樹】

【程式碼如下】

class Solution {
    public int prevIndex=0;
    //找到preorder的prevIndex下標元素在inorder中的位置
    public int findIndex(int[] preorder,int[] inorder,int inbegin,int inend){
        for(int i=inbegin;i<=inend;++i){
            if(inorder[i]==preorder[prevIndex]){
                return i;
            }
        }
         return -1;
    }
    //建立二元樹
    public TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend){
        if(inbegin>inend){
            return null;
        }
        TreeNode root=new TreeNode(preorder[prevIndex]);
        int index=findIndex(preorder,inorder,inbegin,inend);
        prevIndex++;
        root.left=buildTreeChild(preorder,inorder,inbegin,index-1);
        root.right=buildTreeChild(preorder,inorder,index+1,inend);
        return root;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }
}

6、二元樹建立字串

【OJ連結】

字串拼接，可以建立StringBuilder方便拼接，先將根節點拼接入字串，如果其左子樹不為空，拼接左括號，遞迴左子樹，遞迴完後拼接右括號；左樹為空的情況下，如果右樹也為空，直接拼接右括號，否則，我們拼接空括號，遞迴右子樹，之後再拼接右括號。

【程式碼如下】

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

7、非遞迴實現二元樹前序遍歷

【OJ連結】

可以用棧來實現。定義一個棧，將根節點入棧後，去入棧左節點、左節點的左節點……直到為空，去除棧頂元素，入棧其右節點，知道為空，以此迴圈即可。(中序遍歷和前序遍歷思路相同）

【程式碼如下】

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        while(cur!=null||!stack.empty()){
            while(cur!=null){
                stack.push(cur);
                list.add(cur.val);
                cur=cur.left;
            }
            TreeNode node=stack.pop();
            cur=node.right;
        }
        return list;
    }
}

8、非遞迴實現二元樹後序遍歷

【OJ連結】

初始化一個空棧。當【根節點不為空】或者【棧不為空】時，從根節點開。每次將當前節點壓入棧中，如果當前節點有左子樹，就往左子樹跑，沒有左子樹就往右子樹跑。若當前節點無左子樹也無右子樹，從棧中彈出該節點，如果當前節點是上一個節點（即彈出該節點後的棧頂元素）的左節點，嘗試存取上個節點的右子樹，如果不是，那當前棧的棧頂元素繼續彈出。

【程式碼如下】

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        TreeNode prev=null;
        while(cur!=null||!stack.empty()){
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
             }
            TreeNode top=stack.peek();
            if(top.right==null||top.right==prev){
                list.add(top.val);
                stack.pop();
                prev=top;
            }else{
                cur=top.right;
            }
        }
      return list;
    }
}

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

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

目錄

1、對稱二元樹

2、建立並遍歷二元樹

3、二元樹中兩節點最近公共祖先

4、二元搜尋樹與雙向連結串列

5、根據前序和中序遍歷結果建立二元樹

6、二元樹建立字串

7、非遞迴實現二元樹前序遍歷

8、非遞迴實現二元樹後序遍歷

熱門文章