【刷算法】二叉樹(shù)中序遍歷的下一個(gè)結(jié)點(diǎn)

luckyyulin 發(fā)布于2019-08-22 18:44 / 3460人閱讀

摘要：題目描述給定一個(gè)二叉樹(shù)和其中的一個(gè)結(jié)點(diǎn)，請(qǐng)找出中序遍歷順序的下一個(gè)結(jié)點(diǎn)并且返回。分析對(duì)于二叉樹(shù)中序遍歷來(lái)說(shuō)，某的下一個(gè)節(jié)點(diǎn)可以分為以下幾種情況不為時(shí)，根據(jù)中序遍歷的定義，下一個(gè)節(jié)點(diǎn)則是右子樹(shù)里最左邊的節(jié)點(diǎn)。

題目描述

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

分析

對(duì)于二叉樹(shù)中序遍歷來(lái)說(shuō)，某node的下一個(gè)節(jié)點(diǎn)可以分為以下幾種情況：

node.right 不為 null時(shí)，根據(jù)中序遍歷的定義，下一個(gè)節(jié)點(diǎn)則是node右子樹(shù)里最左邊的節(jié)點(diǎn)。

node.right 為 null時(shí)，考察node是否為node.parent的左節(jié)點(diǎn)，如果是的話，node的下一個(gè)節(jié)點(diǎn)就是node.parent；否則，考察node.parent是否為node.parent.parent的左節(jié)點(diǎn)，依次這樣向上探索下去。

代碼實(shí)現(xiàn)

/*function TreeLinkNode(x){
    this.val = x;
    this.left = null;
    this.right = null;
    this.next = null;
}*/
function GetNext(node)
{
    if(node === null)
        return null;
    if(node.right !== null){
        node = node.right;
        while(node.left !== null){
            node = node.left;
        }
        return node;
    }else{
        while(node.next !== null){
            if(node === node.next.left)
                return node.next;
            node =  node.next;
        }
    }
    return null;
}

云服務(wù)器 GPU云服務(wù)器二叉樹(shù) 求結(jié)點(diǎn)個(gè)數(shù) 二叉樹(shù)遍歷二叉樹(shù)的遍歷 JS二叉樹(shù)遍歷

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/96154.html

相關(guān)文章

數(shù)據(jù)結(jié)構(gòu)與算法（樹(shù)） --javascript語(yǔ)言描述

摘要：重建二叉樹(shù)輸入某二叉樹(shù)的前序遍歷和中序遍歷的結(jié)果，請(qǐng)重建出該二叉樹(shù)。所以先通過(guò)前序遍歷找出根節(jié)點(diǎn)，然后將中序遍歷分為左右子樹(shù)兩組，最后對(duì)于每個(gè)子樹(shù)依次遞歸調(diào)用。重建二叉樹(shù) 輸入某二叉樹(shù)的前序遍歷和中序遍歷的結(jié)果，請(qǐng)重建出該二叉樹(shù)。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}...

henry14 2019-08-26 11:44 評(píng)論0 收藏0
?算法入門?《二叉樹(shù) - 二叉搜索樹(shù)》簡(jiǎn)單05 —— LeetCode 897. 遞增順序搜索樹(shù)

文章目錄一、題目1、題目描述2、基礎(chǔ)框架3、原題鏈接二、解題報(bào)告1、思路分析2、時(shí)間復(fù)雜度3、代碼詳解三、本題小知識(shí)四、加群須知一、題目 1、題目描述 ??給你一棵二叉搜索樹(shù)，請(qǐng)按中序遍歷將其重新排列為一棵遞增順序搜索樹(shù)，使樹(shù)中最左邊的節(jié)點(diǎn)成為樹(shù)的根節(jié)點(diǎn)，并且每個(gè)節(jié)點(diǎn)沒(méi)有左子節(jié)點(diǎn)，只有一個(gè)右子節(jié)點(diǎn)。??樣例輸入： [5,3,6,2,4,null,8,1,null,null,nu...

Soarkey 2021-09-10 10:51 評(píng)論0 收藏0
數(shù)據(jù)結(jié)構(gòu)與算法:二叉樹(shù)算法

摘要：因此，根據(jù)題目給出的先序遍歷和中序遍歷，可以畫出二叉樹(shù)選參考數(shù)據(jù)結(jié)構(gòu)與算法描述實(shí)現(xiàn)二叉樹(shù)算法淺談數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)慕課網(wǎng)實(shí)現(xiàn)二叉樹(shù)算法前端樹(shù)控件騰訊軟件開(kāi)發(fā)面試題內(nèi)容銜接上一章數(shù)據(jù)結(jié)構(gòu)與算法:常見(jiàn)排序算法內(nèi)容提要什么是樹(shù) 　　- 為什么使用樹(shù) 二叉樹(shù) 二叉查找樹(shù) 紅黑樹(shù) Ｂ、Ｂ＋樹(shù) 堆伸展樹(shù) 樹(shù) 可以點(diǎn)擊鏈接感受下筆者用d3.js畫的tree https://codepen...

Little_XM 2019-08-22 11:09 評(píng)論0 收藏0
js數(shù)據(jù)結(jié)構(gòu)和算法（三）二叉樹(shù)

摘要：同樣結(jié)點(diǎn)樹(shù)的二叉樹(shù)，完全二叉樹(shù)的深度最小。二叉樹(shù)每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子，所以為它設(shè)計(jì)一個(gè)數(shù)據(jù)域和兩個(gè)指針域是比較自然的想法，我們稱這樣的鏈表叫做二叉鏈表。二叉樹(shù)的概念二叉樹(shù)（Binary Tree）是n（n>=0）個(gè)結(jié)點(diǎn)的有限集合，該集合或者為空集（空二叉樹(shù)），或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的、分別稱為根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。 showImg(https://seg...

DesGemini 2019-08-21 10:20 評(píng)論0 收藏0
樹(shù)和樹(shù)的算法

摘要：樹(shù)和樹(shù)的算法一樹(shù)樹(shù)的概念樹(shù)英語(yǔ)是一種抽象數(shù)據(jù)類型或是實(shí)作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來(lái)模擬具有樹(shù)狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。一種時(shí)間復(fù)雜度額外空間復(fù)雜度的二叉樹(shù)的遍歷方式，為二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)。樹(shù)和樹(shù)的算法一、樹(shù) 1.1 樹(shù)的概念樹(shù)（英語(yǔ)：tree）是一種抽象數(shù)據(jù)類型（ADT）或是實(shí)作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來(lái)模擬具有樹(shù)狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。它是由n（n>=1）個(gè)有限節(jié)點(diǎn)組成一個(gè)...

RaoMeng 2019-08-19 11:08 評(píng)論0 收藏0