Java?數(shù)據(jù)結(jié)構(gòu)進(jìn)階二叉樹題集下

更新時間：2022年04月01日 18:17:02 作者：Pretend..

二叉樹可以簡單理解為對于一個節(jié)點來說，最多擁有一個上級節(jié)點，同時最多具備左右兩個下級節(jié)點的數(shù)據(jù)結(jié)構(gòu)。本文將帶你通過實際題目來熟練掌握

1、對稱二叉樹
2、創(chuàng)建并遍歷二叉樹
3、二叉樹中兩節(jié)點最近公共祖先
4、二叉搜索樹與雙向鏈表
5、根據(jù)前序和中序遍歷結(jié)果創(chuàng)建二叉樹
6、二叉樹創(chuàng)建字符串
7、非遞歸實現(xiàn)二叉樹前序遍歷
8、非遞歸實現(xiàn)二叉樹后序遍歷

1、對稱二叉樹

分為以下幾種情況：

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

【代碼如下】

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、創(chuàng)建并遍歷二叉樹

【OJ鏈接】

【題目描述】

讀入用戶輸入的一串先序遍歷字符串，根據(jù)此字符串建立一個二叉樹（以指針方式存儲）。例如如下的先序遍歷字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空樹。建立起此二叉樹以后，再對二叉樹進(jìn)行中序遍歷，輸出遍歷結(jié)果。

關(guān)于這個題，完全從零開始，我們需要定義（1）二叉樹的節(jié)點，（2）中序遍歷的函數(shù)，（3）根據(jù)先序遍歷字符串創(chuàng)建二叉樹的函數(shù)，（4）主函數(shù)。創(chuàng)建節(jié)點、中序遍歷、主函數(shù)不用多說。主要說一下根據(jù)先序遍歷字符串來創(chuàng)建二叉樹的過程：

遍歷字符串，#表示空，就分為以下兩種情況：如果字符不為空，我們需要創(chuàng)建根節(jié)點，然后遞歸創(chuàng)建其的左右子樹；否則，直接跳過即可。

【代碼如下】

import java.util.Scanner;
    //定義二叉樹的節(jié)點
    class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;
        public  TreeNode(char val){
            this.val=val;
        }
    }
public class Main {
    //根據(jù)先序遍歷字符串創(chuàng)建二叉樹
    public static int i=0;
    public static TreeNode createTree(String s){
        TreeNode root=null;
        //字符不為空的情況下，創(chuàng)建根節(jié)點
        if(s.charAt(i)!='#'){
            root=new TreeNode(s.charAt(i));
            i++;
            //遞歸創(chuàng)建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、二叉樹中兩節(jié)點最近公共祖先

【OJ鏈接】

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

【代碼如下】

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鏈接】

二叉搜索樹：任何節(jié)點的左子樹小于右子樹

將二叉搜索樹轉(zhuǎn)換為有序的雙向鏈表：

二叉搜索樹的中序遍歷結(jié)果為有序的。所以我們只需要寫一個中序遍歷，在其中實現(xiàn)其節(jié)點左右指向的改變即可。首先我們需要一個前驅(qū)節(jié)點prev來保存每個節(jié)點的左節(jié)點，初始為null，因為是雙向鏈表，所以prev還需要指向它的右節(jié)點，如果其為空，則不用。

【代碼如下】

public class Solution {
    public TreeNode prev=null;
    //中序遍歷二叉樹
    public void inorderTree(TreeNode root){
        if(root==null){
            return ;
        }
        inorderTree(root.left);
        //處理二叉樹的左右節(jié)點
        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、根據(jù)前序和中序遍歷結(jié)果創(chuàng)建二叉樹

【OJ鏈接】

給出一個二叉樹的前序遍歷和中序遍歷的結(jié)果，根據(jù)其創(chuàng)建二叉樹：

我們知道，前序遍歷的第一個元素（prev）一定是根節(jié)點（從前往后遍歷），所以在中序遍歷中找到prev，則左邊元素為左子樹元素，右邊元素為右子樹，創(chuàng)建根節(jié)點，遞歸創(chuàng)建左子樹和右子樹。注意一定要先創(chuàng)建左子樹，因為先序遍歷的因素，先序遍歷數(shù)組的下一個元素一定是左子樹的根節(jié)點?！救绻歉鶕?jù)后序遍歷和中序遍歷創(chuàng)建二叉樹，則后序遍歷的數(shù)組需要從后往前遍歷，還有，一定要先遞歸創(chuàng)建右子樹】

【代碼如下】

class Solution {
    public int prevIndex=0;
    //找到preorder的prevIndex下標(biāo)元素在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;
    }
    //創(chuàng)建二叉樹
    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、二叉樹創(chuàng)建字符串

【OJ鏈接】

字符串拼接，可以創(chuàng)建StringBuilder方便拼接，先將根節(jié)點拼接入字符串，如果其左子樹不為空，拼接左括號，遞歸左子樹，遞歸完后拼接右括號；左樹為空的情況下，如果右樹也為空，直接拼接右括號，否則，我們拼接空括號，遞歸右子樹，之后再拼接右括號。

【代碼如下】

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、非遞歸實現(xiàn)二叉樹前序遍歷

【OJ鏈接】

可以用棧來實現(xiàn)。定義一個棧，將根節(jié)點入棧后，去入棧左節(jié)點、左節(jié)點的左節(jié)點……直到為空，去除棧頂元素，入棧其右節(jié)點，知道為空，以此循環(huán)即可。(中序遍歷和前序遍歷思路相同）

【代碼如下】

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、非遞歸實現(xiàn)二叉樹后序遍歷

【OJ鏈接】

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

【代碼如下】

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

到此這篇關(guān)于Java 數(shù)據(jù)結(jié)構(gòu)進(jìn)階二叉樹題集下的文章就介紹到這了,更多相關(guān)Java 二叉樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: