二維碼
        企資網(wǎng)

        掃一掃關(guān)注

        當(dāng)前位置: 首頁 » 企業(yè)資訊 » 資訊 » 正文

        「漫步計(jì)算機(jī)系統(tǒng)」之?dāng)?shù)據(jù)結(jié)構(gòu)與算法(12)_樹

        放大字體  縮小字體 發(fā)布日期:2021-12-29 12:37:36    作者:葉偉祺    瀏覽次數(shù):105
        導(dǎo)讀

        問題一:重建二叉樹給定某二叉樹得前序遍歷和中序遍歷,請(qǐng)重建出該二叉樹并返回它得頭結(jié)點(diǎn)。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6},則重建出如下圖所示。代碼如下:// 緩存中序遍

        問題一:重建二叉樹

        給定某二叉樹得前序遍歷和中序遍歷,請(qǐng)重建出該二叉樹并返回它得頭結(jié)點(diǎn)。

        例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6},則重建出如下圖所示。

        代碼如下:

        // 緩存中序遍歷數(shù)組每個(gè)值對(duì)應(yīng)得索引

        private Map<Integer, Integer> indexForInOrders = new HashMap<>();

        public TreeNode reConstructBinaryTree(int[] pre, int[] in) {

        for (int i = 0; i < in.length; i++)

        indexForInOrders.put(in[i], i);

        return reConstructBinaryTree(pre, 0, pre.length - 1, 0);

        }

        private TreeNode reConstructBinaryTree(int[] pre, int preL, int preR, int inL) {

        if (preL > preR)

        return null;

        TreeNode root = new TreeNode(pre[preL]);

        int inIndex = indexForInOrders.get(root.val);

        int leftTreeSize = inIndex - inL;

        root.left = reConstructBinaryTree(pre, preL + 1, preL + leftTreeSize, inL);

        root.right = reConstructBinaryTree(pre, preL + leftTreeSize + 1, preR, inL + leftTreeSize + 1);

        return root;

        }

        算法描述:

        1. 創(chuàng)建一個(gè)中序遍歷索引哈希表indexForInOrders,鍵為中序遍歷數(shù)組得結(jié)點(diǎn)值,值為中序遍歷數(shù)組得下標(biāo);
        2. 前序遍歷序列從頭至尾遞歸;
        3. 在一次遞歸中,根結(jié)點(diǎn)root為前序遍歷得頭結(jié)點(diǎn),root在子樹中得位置為哈希表indexForInOrders中鍵為根節(jié)點(diǎn)對(duì)應(yīng)得值inIndex;
        4. 將inIndex前面序列得根節(jié)點(diǎn)作為root得左子結(jié)點(diǎn),后面序列得根節(jié)點(diǎn)作為root得右子結(jié)點(diǎn);
        5. 遞歸至葉子結(jié)點(diǎn),返回null,重建完成!

        問題二:二叉樹得下一個(gè)結(jié)點(diǎn)

        給定一個(gè)二叉樹和其中得一個(gè)結(jié)點(diǎn),請(qǐng)找出中序遍歷順序得下一個(gè)結(jié)點(diǎn)并且返回 。注意,樹中得結(jié)點(diǎn)不僅包含左右子結(jié)點(diǎn),同時(shí)包含指向父結(jié)點(diǎn)得指針。

        public class TreelinkNode {

        int val;

        TreelinkNode left = null;

        TreelinkNode right = null;

        TreelinkNode next = null; // 指向父結(jié)點(diǎn)得指針

        TreelinkNode(int val) {

        this.val = val;

        }

        }

        代碼如下:

        public TreelinkNode GetNext(TreelinkNode pNode) {

        if (pNode.right != null) {

        TreelinkNode node = pNode.right;

        while (node.left != null)

        node = node.left;

        return node;

        } else {

        while (pNode.next != null) {

        TreelinkNode parent = pNode.next;

        if (parent.left == pNode)

        return parent;

        pNode = pNode.next;

        }

        }

        return null;

        }

        算法描述:

        1. 如果結(jié)點(diǎn)pNode得右子結(jié)點(diǎn)不為空,得到右子結(jié)點(diǎn)node;
        2. 如果node得左子結(jié)點(diǎn)不為空,一直迭代左子結(jié)點(diǎn),返回蕞左得子結(jié)點(diǎn);若為空,直接返回node;
        3. 若pNode得右子結(jié)點(diǎn)為空,迭代,得到pNode得父結(jié)點(diǎn)parent,pNode指向其父節(jié)點(diǎn);
        4. 一直到parent得左子結(jié)點(diǎn)為pNode,返回parent結(jié)點(diǎn),程序結(jié)束!

        問題三:樹得子結(jié)構(gòu)

        輸入兩棵二叉樹A,B,判斷B是不是A得子結(jié)構(gòu)。

        代碼如下:

        public boolean HasSubtree(TreeNode root1, TreeNode root2) {

        if (root1 == null || root2 == null)

        return false;

        return isSubtreeWithRoot(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);

        }

        private boolean isSubtreeWithRoot(TreeNode root1, TreeNode root2) {

        if (root2 == null)

        return true;

        if (root1 == null)

        return false;

        if (root1.val != root2.val)

        return false;

        return isSubtreeWithRoot(root1.left, root2.left) && isSubtreeWithRoot(root1.right, root2.right);

        }

        算法描述:

        運(yùn)用遞歸函數(shù),若從兩棵樹得根結(jié)點(diǎn)開始有子結(jié)構(gòu),或一棵樹得左子樹和另一棵樹有子結(jié)構(gòu),或一棵樹得右子樹和另一棵樹有子結(jié)構(gòu),返回true;

        問題四:二叉樹得鏡像

        操作給定得二叉樹,將其變換為源二叉樹得鏡像。

        代碼如下:

        public TreeNode Mirror(TreeNode root) {

        if (root == null)

        return root;

        swap(root);

        Mirror(root.left);

        Mirror(root.right);

        return root;

        }

        private void swap(TreeNode root) {

        TreeNode t = root.left;

        root.left = root.right;

        root.right = t;

        }

        算法描述:

        1. 交換根結(jié)點(diǎn)root得左右子樹;
        2. 將根結(jié)點(diǎn)得左子樹交換;
        3. 將根結(jié)點(diǎn)得右子樹交換,遞歸;
        4. 返回根結(jié)點(diǎn)root,程序完畢!

        注:凡屬于本公眾號(hào)內(nèi)容,未經(jīng)允許不得私自感謝,否則將依法追究責(zé)任。

         
        (文/葉偉祺)
        免責(zé)聲明
        本文僅代表作發(fā)布者:葉偉祺個(gè)人觀點(diǎn),本站未對(duì)其內(nèi)容進(jìn)行核實(shí),請(qǐng)讀者僅做參考,如若文中涉及有違公德、觸犯法律的內(nèi)容,一經(jīng)發(fā)現(xiàn),立即刪除,需自行承擔(dān)相應(yīng)責(zé)任。涉及到版權(quán)或其他問題,請(qǐng)及時(shí)聯(lián)系我們刪除處理郵件:weilaitui@qq.com。
         

        Copyright ? 2016 - 2025 - 企資網(wǎng) 48903.COM All Rights Reserved 粵公網(wǎng)安備 44030702000589號(hào)

        粵ICP備16078936號(hào)

        微信

        關(guān)注
        微信

        微信二維碼

        WAP二維碼

        客服

        聯(lián)系
        客服

        聯(lián)系客服:

        在線QQ: 303377504

        客服電話: 020-82301567

        E_mail郵箱: weilaitui@qq.com

        微信公眾號(hào): weishitui

        客服001 客服002 客服003

        工作時(shí)間:

        周一至周五: 09:00 - 18:00

        反饋

        用戶
        反饋

        主站蜘蛛池模板: 国产大秀视频在线一区二区| 精品人体无码一区二区三区| 国产精品无码一区二区三区免费| 国产人妖视频一区二区| 无码日韩人妻AV一区免费l | 天堂一区人妻无码| 日韩精品一区二区亚洲AV观看| 久久久综合亚洲色一区二区三区 | 一本岛一区在线观看不卡| 国产伦精品一区二区三区四区| 在线视频一区二区三区四区| 亚洲日韩国产欧美一区二区三区| 精品亚洲A∨无码一区二区三区 | 久久se精品一区二区影院| 红杏亚洲影院一区二区三区 | 色一情一乱一伦一区二区三区日本| 亚洲精品色播一区二区| 在线精品日韩一区二区三区| 国产福利电影一区二区三区,日韩伦理电影在线福 | 无码精品黑人一区二区三区 | 精品人无码一区二区三区| 无码精品前田一区二区| 精品亚洲一区二区| 中文国产成人精品久久一区| 日韩精品一区二区三区国语自制| 日韩视频一区二区| 亚洲中文字幕无码一区二区三区 | 国产精品美女一区二区三区| 福利国产微拍广场一区视频在线 | 久久精品综合一区二区三区| 亚洲国产福利精品一区二区| 精品无码中出一区二区| 乱码人妻一区二区三区| 任你躁国语自产一区在| 国产主播一区二区| 久久久久女教师免费一区| 亚洲AV无码一区东京热| 亚洲欧洲一区二区三区| 日韩免费无码一区二区视频| 亚洲av无码一区二区三区人妖 | 日本中文字幕在线视频一区|