二維碼
        企資網(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ù):112
        導(dǎo)讀

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

        問題一:重建二叉樹

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

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

        代碼如下:

        // 緩存中序遍歷數(shù)組每個值對應(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)建一個中序遍歷索引哈希表indexForInOrders,鍵為中序遍歷數(shù)組得結(jié)點(diǎn)值,值為中序遍歷數(shù)組得下標(biāo);
        2. 前序遍歷序列從頭至尾遞歸;
        3. 在一次遞歸中,根結(jié)點(diǎn)root為前序遍歷得頭結(jié)點(diǎn),root在子樹中得位置為哈希表indexForInOrders中鍵為根節(jié)點(diǎn)對應(yīng)得值inIndex;
        4. 將inIndex前面序列得根節(jié)點(diǎn)作為root得左子結(jié)點(diǎn),后面序列得根節(jié)點(diǎn)作為root得右子結(jié)點(diǎn);
        5. 遞歸至葉子結(jié)點(diǎn),返回null,重建完成!

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

        給定一個二叉樹和其中得一個結(jié)點(diǎn),請找出中序遍歷順序得下一個結(jié)點(diǎn)并且返回 。注意,樹中得結(jié)點(diǎn)不僅包含左右子結(jié)點(diǎn),同時包含指向父結(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,程序完畢!

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

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

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

        粵ICP備16078936號

        微信

        關(guān)注
        微信

        微信二維碼

        WAP二維碼

        客服

        聯(lián)系
        客服

        聯(lián)系客服:

        在線QQ: 303377504

        客服電話: 020-82301567

        E_mail郵箱: weilaitui@qq.com

        微信公眾號: weishitui

        客服001 客服002 客服003

        工作時間:

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

        反饋

        用戶
        反饋

        主站蜘蛛池模板: 立川理惠在线播放一区| 亚洲AV日韩综合一区| 国产福利无码一区在线| 成人国产精品一区二区网站| 亚洲一区综合在线播放| 国产精品无码一区二区三区在| 久久精品一区二区国产| 全国精品一区二区在线观看| 中文字幕一区在线观看视频| 国产自产V一区二区三区C| 三级韩国一区久久二区综合| 无码aⅴ精品一区二区三区| 日韩国产精品无码一区二区三区| 日本一区二区在线不卡| 51视频国产精品一区二区| 久久精品一区二区免费看| 国产精品免费大片一区二区| 国产免费私拍一区二区三区| 中文字幕日韩精品一区二区三区| 色欲精品国产一区二区三区AV| 99久久精品国产免看国产一区| 日韩十八禁一区二区久久| 日韩一区二区三区电影在线观看| 日韩一区二区三区射精| 毛片一区二区三区| 亚洲sm另类一区二区三区| 中文字幕乱码一区久久麻豆樱花 | 69福利视频一区二区| 看电影来5566一区.二区| 中文字幕一区二区三区免费视频| 国产视频福利一区| 国产精品盗摄一区二区在线| 国产一区韩国女主播| 国产一区二区三区樱花动漫| 日韩一区二区三区免费体验| 精品女同一区二区| 久久se精品一区二区影院| 亚洲毛片不卡av在线播放一区| 国产综合无码一区二区色蜜蜜| 国产一区风间由美在线观看| 久久精品一区二区三区中文字幕 |