【刷算法】二叉樹中序遍歷的下一個結(jié)點

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

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

題目描述

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

分析

對于二叉樹中序遍歷來說，某node的下一個節(jié)點可以分為以下幾種情況：

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

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

代碼實現(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;
}

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

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

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/96154.html

相關(guān)文章

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

摘要：重建二叉樹輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹。所以先通過前序遍歷找出根節(jié)點，然后將中序遍歷分為左右子樹兩組，最后對于每個子樹依次遞歸調(diào)用。重建二叉樹輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹。假設(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 評論0 收藏0
?算法入門?《二叉樹 - 二叉搜索樹》簡單05 —— LeetCode 897. 遞增順序搜索樹

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

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

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

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

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

DesGemini 2019-08-21 10:20 評論0 收藏0
樹和樹的算法

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

RaoMeng 2019-08-19 11:08 評論0 收藏0