Java LeetCode篇-深入了解二叉樹的經(jīng)典解法（多種方式實(shí)現(xiàn)：構(gòu)造二叉樹）

這篇具有很好參考價(jià)值的文章主要介紹了Java LeetCode篇-深入了解二叉樹的經(jīng)典解法（多種方式實(shí)現(xiàn)：構(gòu)造二叉樹）。希望對大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

??博客主頁：?【小扳_-CSDN博客】
?感謝大家點(diǎn)贊??收藏?評論????

Java LeetCode篇-深入了解二叉樹的經(jīng)典解法（多種方式實(shí)現(xiàn)：構(gòu)造二叉樹）,Java LeetCode篇,leetcode,職場和發(fā)展,java,數(shù)據(jù)結(jié)構(gòu)

文章目錄

????????1.0 從前序與中序遍歷序列來構(gòu)造二叉樹

? ? ? ? 1.1 實(shí)現(xiàn)從前序與中序遍歷序列來構(gòu)造二叉樹思路? ?

? ? ? ? 1.2 代碼實(shí)現(xiàn)從前序與中序遍歷序列來構(gòu)造二叉樹

? ? ? ? 2.0 從中序與后序遍歷序列構(gòu)造二叉樹

? ? ? ? 2.1 實(shí)現(xiàn)從中序與后序遍歷序列后遭二叉樹思路

? ? ? ? 2.2 代碼實(shí)現(xiàn)從中序與后序遍歷序列來構(gòu)造二叉樹

? ? ? ? 3.0 根據(jù)后綴表達(dá)式創(chuàng)建二叉樹

? ? ? ? 3.1 實(shí)現(xiàn)后綴表達(dá)式創(chuàng)建二叉樹思路

? ? ? ? 3.2 代碼實(shí)現(xiàn)后綴表達(dá)式創(chuàng)建二叉樹

? ? ? ? ?4.0 相同的樹

? ? ? ? 4.1 實(shí)現(xiàn)判斷兩顆樹是否相同思路

? ? ? ? 4.2 代碼實(shí)現(xiàn)相同樹

? ? ? ? ?5.0 另一顆樹的子樹

????????5.1 實(shí)現(xiàn)判斷是否為另一顆樹的子樹

????????5.2 代碼實(shí)現(xiàn)判斷是否為另一顆樹的子樹

????????1.0 從前序與中序遍歷序列來構(gòu)造二叉樹

題目：

????????給定兩個(gè)整數(shù)數(shù)組?preorder?和?inorder?，其中?preorder?是二叉樹的先序遍歷，?inorder?是同一棵樹的中序遍歷，請構(gòu)造二叉樹并返回其根節(jié)點(diǎn)。

示例 1:
輸入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
輸出: [3,9,20,null,null,15,7]
OJ鏈接：

105.?從前序與中序遍歷序列構(gòu)造二叉樹

? ? ? ? 1.1 實(shí)現(xiàn)從前序與中序遍歷序列來構(gòu)造二叉樹思路? ?

????????具體思路為：前序遍歷的流程先是訪問根節(jié)點(diǎn)，到左子樹，再到右子樹的順序；中序遍歷的流程先是左子樹，到訪問根節(jié)點(diǎn)，再到右子樹。因此，在前序的序列中的第一個(gè)元素就是該樹的根節(jié)點(diǎn)的值，然后再通過中序的序列中遍歷找根節(jié)點(diǎn)。接著就可以將其中序的序列進(jìn)行拆分，在中序序列中根節(jié)點(diǎn)的值的左邊部分的序列為左子樹，在中序序列中根節(jié)點(diǎn)的值的右邊部分序列為右子樹。又接著將前序序列進(jìn)行拆分，從索引為 1 開始，長度為：與中序序列中左子樹的序列數(shù)量是一致的，將這一部分稱為左子樹；從索引（1+長度）開始到該序列的結(jié)束，將這一部分稱為右子樹。接下來就是子問題了，通過遞歸，找到當(dāng)前節(jié)點(diǎn)的左右子樹。

? ? ? ?具體例子：前序序列 pre = {3,9,20,15,7}，中序序列 in = {9,3,15,20,7} 。先找到該樹的節(jié)點(diǎn)值 int rootValue = pre[0]， TreeNode root = new TreeNode(rootValue)，創(chuàng)建該樹的根節(jié)點(diǎn)。接著對中序序列遍歷來找到根節(jié)點(diǎn)的值，i == 1 ，在中序序列中找左右子樹：在索引在該區(qū)間 [0,1）是節(jié)點(diǎn)的左子樹，而在索引為?[2,5）區(qū)間是節(jié)點(diǎn)的右子樹。在前序序列中找左右子樹：在索引為 [1,2）是該節(jié)點(diǎn)的左子樹，而在索引為 [2,5）區(qū)間是節(jié)點(diǎn)的右子樹。

? ? ? ? 子問題：那么現(xiàn)在得到了左子樹的前序序列 pre = { 9 } ，左子樹的中序序列 in = { 9 }，接下來的流程跟以上的流程是一樣的，先找到該子樹的根節(jié)點(diǎn)值 9 ，然后創(chuàng)建一個(gè)值為 9 的根節(jié)點(diǎn)。接著，遍歷中序序列來找到根節(jié)點(diǎn)的值，該根節(jié)點(diǎn)的左部分就是左子樹，該節(jié)點(diǎn)的右部分就是右子樹。那么這里的左右子樹都為空，因此節(jié)點(diǎn)為 9 的根節(jié)點(diǎn)沒有左右子樹了。

? ? ? ? 往上回溯：來到根節(jié)點(diǎn)值為 3 的節(jié)點(diǎn)?，F(xiàn)在得到了右子樹的前序序列 pre = {20,15,7} ，右子樹的中序序列 in = {15,20,7} ，接下來的過程是一摸一樣的，先找到該子樹的根節(jié)點(diǎn)值為 20 ，創(chuàng)建值為 20 的根節(jié)點(diǎn)。然后在中序序列中進(jìn)行遍歷找到根節(jié)點(diǎn)的左右子樹：左子樹序列為 {15}，右子樹序列為 {7}，接著在前序序列中找左右子樹：左子樹序列為 {15}，右子樹序列為 {7} 。又得到了左右前中序列，按同樣的道理繼續(xù)下去即可，通過上面的結(jié)論，當(dāng)左子樹前序 {15} 與左子樹中序 {15} 一樣時(shí)，那么在當(dāng)前的節(jié)點(diǎn)值為 15 的根節(jié)點(diǎn)沒有左右子樹了。同理，當(dāng)右子樹前序 {7} 與右子樹中序 {7} 一樣時(shí)，那么在當(dāng)前的節(jié)點(diǎn)值為 7 的根節(jié)點(diǎn)沒有左右子樹了。

? ? ? ? 最后回溯，根節(jié)點(diǎn)值為 20 的左子樹的根節(jié)點(diǎn)為 15，右子樹的根節(jié)點(diǎn)為 7 ，鏈接起來，一直回溯到結(jié)束返回的最后的節(jié)點(diǎn)就是該樹的根節(jié)點(diǎn)（值為 1 的根節(jié)點(diǎn)）。

? ? ? ? 需要注意的是：注意左閉右開。因?yàn)槭峭活w樹，在前序中的左右子樹的長度跟中序中的左右子樹的長度是一樣的。

? ? ? ? 1.2 代碼實(shí)現(xiàn)從前序與中序遍歷序列來構(gòu)造二叉樹

    //根據(jù)前序與中序來構(gòu)造二叉樹
    public TreeNode prevAndInOrderConstructTree(int[] prevOrder, int[] inOrder) {
        if (prevOrder.length == 0) {
            return null;
        }
        int rootValue = prevOrder[0];
        TreeNode root = new TreeNode(rootValue);
        for (int i = 0; i < inOrder.length; i++) {
            if (inOrder[i] == rootValue) {
                int[] inLeft = Arrays.copyOfRange(inOrder,0,i);
                int[] inRight = Arrays.copyOfRange(inOrder,i+1,inOrder.length);

                int[] prevLeft = Arrays.copyOfRange(prevOrder,1,i + 1);
                int[] prevRight = Arrays.copyOfRange(prevOrder,i+1,inOrder.length);

                root.left = prevAndInOrderConstructTree(prevLeft,inLeft);
                root.right = prevAndInOrderConstructTree(prevRight,inRight);
            }
        }
        return root;
    }

? ? ? ? 只要某一個(gè)序列無論是前序或者是中序序列的長度為 0 ，都代表創(chuàng)建二叉樹過程結(jié)束了。

? ? ? ? 2.0 從中序與后序遍歷序列構(gòu)造二叉樹

題目：

????????給定兩個(gè)整數(shù)數(shù)組?inorder?和?postorder?，其中?inorder?是二叉樹的中序遍歷，?postorder?是同一棵樹的后序遍歷，請你構(gòu)造并返回這顆?二叉樹?。

示例 1:
輸入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
輸出：[3,9,20,null,null,15,7]
OJ鏈接：

106.?從中序與后序遍歷序列構(gòu)造二叉樹

? ? ? ? 2.1 實(shí)現(xiàn)從中序與后序遍歷序列后遭二叉樹思路

? ? ? ? 具體思路為：中序的序列先訪問左子樹，再訪問根節(jié)點(diǎn)，最后到右子樹。后序的序列先訪問左子樹，再訪問右子樹，最后才到根節(jié)點(diǎn)。因此，可以從后序序列中的最后一個(gè)元素得到根節(jié)點(diǎn)的值，然后利用該值來創(chuàng)建根節(jié)點(diǎn)。接著，在中序序列中遍歷查找根節(jié)點(diǎn)的值，在中序序列中根節(jié)點(diǎn)值左邊的序列為左子樹序列，在中序序列中根節(jié)點(diǎn)的右邊為右子樹的序列。再接著再后序中獲取左子樹的序列：從索引為 0 開始長度是中序序列得到的左子樹的長度；從后序序列中獲取右子樹序列：除了左子樹的序列和根節(jié)點(diǎn)值元素，其余就是右子樹的序列了。接下來就是子問題了，遞歸下去，返回當(dāng)前的根節(jié)點(diǎn)。

? ? ? ? 具體例子：中序序列 in = {9,3,15,20,7}，后序序列 post = {9,15,7,20,3}，通過后序得到該樹的根節(jié)點(diǎn)的值 3，由這個(gè)值來創(chuàng)建值為 3 的根節(jié)點(diǎn)。接著通過遍歷中序序列，找到值為 3 來定位左右子樹，左子樹的序列為：{9} ，右子樹的序列為：{15,20,7} 。再從中序序列中定位左右子樹，左子樹為：{9}，右子樹為：{15，7，20} 。現(xiàn)在得到了左右中后序列，中序左子樹：{9} ，后序左子樹：{9}，通過后序得到根節(jié)點(diǎn)，再從中序定位該子樹的根節(jié)點(diǎn)，這里根節(jié)點(diǎn)值為 9 的根節(jié)點(diǎn)的左右子樹均為 null 。接著回溯，返回的該子樹的根節(jié)點(diǎn)。

? ? ? ? 再到右子樹中序 {15,20,7} ，右子樹后序 {15,7,20}，通過后序序列的最后一個(gè)值來創(chuàng)建該子樹的根節(jié)點(diǎn)，在中序中遍歷找到該根節(jié)點(diǎn)的值，定位該節(jié)點(diǎn)的左右子樹。中序的左子樹序列 {15}，右子樹序列 {7}；后序的左子樹序列 {15}，后序的右子樹序列 {7} 。

? ? ? ? 再接著遞歸，得到左子樹中序 {15} ，左子樹后序 {15}。通過后序的最后一個(gè)元素就是根節(jié)點(diǎn)的值來創(chuàng)建該子樹的根節(jié)點(diǎn)，然后在中序中定位該根節(jié)點(diǎn)的左右子樹，這里的左右子樹都為 null ，返回根節(jié)點(diǎn)即可。得到右子樹中序 {7}，右子樹后序 {7}，通過后序的最后一個(gè)元素為根節(jié)點(diǎn)的值來創(chuàng)建該子樹的根節(jié)點(diǎn)，然后在中序中定位該根節(jié)點(diǎn)的左右子樹，恰好，這里的左右子樹都為 null ，返回根節(jié)點(diǎn)即可。

? ? ? ? 最后回溯過程，根節(jié)點(diǎn)值為 1 的節(jié)點(diǎn)的左子樹的根節(jié)點(diǎn)為 9 的節(jié)點(diǎn)，右子樹的根節(jié)點(diǎn)為 20 的節(jié)點(diǎn)。

? ? ? ? 2.2 代碼實(shí)現(xiàn)從中序與后序遍歷序列來構(gòu)造二叉樹

    //根據(jù)中序與后序來構(gòu)造二叉樹
    public TreeNode inAndPostConstructTree(int[] inOrder, int[] postOrder) {

        if (inOrder.length == 0) {
            return null;
        }
        int rootValue = postOrder[postOrder.length-1];
        TreeNode root = new TreeNode(rootValue);
        for (int j = 0; j < inOrder.length; j++) {
            if (rootValue == inOrder[j]) {
                int[] inLeft = Arrays.copyOfRange(inOrder,0,j);
                int[] inRight = Arrays.copyOfRange(inOrder,j+1,inOrder.length);

                int[] postLeft = Arrays.copyOfRange(postOrder,0,j);
                int[] postRight = Arrays.copyOfRange(postOrder,j,postOrder.length-1);

                root.left = inAndPostConstructTree(inLeft,postLeft);
                root.right = inAndPostConstructTree(inRight,postRight);
            }
        }
        return root;

    }

? ? ? ? 需要注意的定位左右子樹的序列長度，中序與后序的左右子樹都是一一對應(yīng)的。也因此，當(dāng)無論任意一個(gè)序列結(jié)束，都代表著構(gòu)造二叉樹過程結(jié)束。

? ? ? ? 3.0 根據(jù)后綴表達(dá)式創(chuàng)建二叉樹

????????后綴表達(dá)式也叫逆波蘭表達(dá)式，是一種不需要括號的表達(dá)式表示方法。在后綴表達(dá)式中，運(yùn)算符總是在操作數(shù)的后面，因此可以通過從左到右掃描表達(dá)式來創(chuàng)建二叉樹。

? ? ? ? 3.1 實(shí)現(xiàn)后綴表達(dá)式創(chuàng)建二叉樹思路

? ? ? ? 具體思路為：若遇到數(shù)字將其壓入棧中；若遇到操作符時(shí)，將棧中的右左元素彈出棧，操作符節(jié)點(diǎn)進(jìn)行鏈接彈出來的左右子樹，需要注意的是，第一個(gè)彈出來的是右操作數(shù)，第二個(gè)才是左操作數(shù)。鏈接完之后，將其壓入棧中即可。循環(huán)結(jié)束條件為：將后綴表達(dá)式遍歷完就結(jié)束。最后返回棧中的棧頂元素，就是該樹的根節(jié)點(diǎn)。

? ? ? ? 3.2 代碼實(shí)現(xiàn)后綴表達(dá)式創(chuàng)建二叉樹

    //根據(jù)后綴表達(dá)式創(chuàng)建二叉樹
    public TreeNode suffixCreateTree(String[] s) {

        LinkedList<TreeNode> stack = new LinkedList<>();
        for (int i = 0; i < s.length; i++) {
            String ch = s[i];
            switch (ch) {
                case "+","-","*","/" -> {
                    TreeNode right = stack.pop();
                    TreeNode left = stack.pop();
                    TreeNode t = new TreeNode(ch);
                    t.right = right;
                    t.left = left;
                    stack.push(t);
                }
                default -> {
                    stack.push(new TreeNode(ch));
                }
            }

        }
        return stack.peek();
    }

? ? ? ? ?4.0 相同的樹

題目：

????????給你兩棵二叉樹的根節(jié)點(diǎn)?p?和?q?，編寫一個(gè)函數(shù)來檢驗(yàn)這兩棵樹是否相同。

如果兩個(gè)樹在結(jié)構(gòu)上相同，并且節(jié)點(diǎn)具有相同的值，則認(rèn)為它們是相同的。

示例 1：
輸入：p = [1,2,3], q = [1,2,3]
輸出：true
OJ鏈接：

100.?相同的樹

? ? ? ? 4.1 實(shí)現(xiàn)判斷兩顆樹是否相同思路

? ? ? ? 具體思路為：使用遞歸實(shí)現(xiàn)，第一種情況：若一個(gè)子樹為 null ，另一個(gè)子樹不為 null ，返回 false ；第二種情況：若兩個(gè)子樹都為 null ，則返回 true 。第三種情況：若兩個(gè)子樹的根節(jié)點(diǎn)的值不相同時(shí)，返回 false 。子過程，判斷完左子樹，還需判斷右子樹。

? ? ? ? 4.2 代碼實(shí)現(xiàn)相同樹

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

? ? ? ? 5.0 另一顆樹的子樹

題目：

????????給你兩棵二叉樹?root?和?subRoot?。檢驗(yàn)?root?中是否包含和?subRoot?具有相同結(jié)構(gòu)和節(jié)點(diǎn)值的子樹。如果存在，返回?true?；否則，返回?false?。

二叉樹?tree?的一棵子樹包括?tree?的某個(gè)節(jié)點(diǎn)和這個(gè)節(jié)點(diǎn)的所有后代節(jié)點(diǎn)。tree?也可以看做它自身的一棵子樹。

示例 1：
輸入：root = [3,4,5,1,2], subRoot = [4,1,2]
輸出：true
OJ鏈接:

572.?另一棵樹的子樹

? ? ? ? ?5.1 實(shí)現(xiàn)判斷是否為另一顆樹的子樹

? ? ? ? 具體思路為：最根本的問題就是判斷是否為相同的樹，判斷該樹的子樹與另一顆子樹是否相同，不斷遞歸下去，只要相同就返回 true 。直到最后遞歸結(jié)束都沒有匹配，則返回 false 。

? ? ? ? 5.2 代碼實(shí)現(xiàn)判斷是否為另一顆樹的子樹

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null) {
            return false;
        }
        if(isSameTree(root,subRoot)) {
            return true;
        }
        if(isSubtree(root.left,subRoot)) {
            return true;
        }
        if(isSubtree(root.right,subRoot)) {
            return true;
        }
        return false;

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

Java LeetCode篇-深入了解二叉樹的經(jīng)典解法（多種方式實(shí)現(xiàn)：構(gòu)造二叉樹）,Java LeetCode篇,leetcode,職場和發(fā)展,java,數(shù)據(jù)結(jié)構(gòu) 文章來源地址http://www.zghlxwxcb.cn/news/detail-753892.html

到了這里，關(guān)于Java LeetCode篇-深入了解二叉樹的經(jīng)典解法（多種方式實(shí)現(xiàn)：構(gòu)造二叉樹）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！