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

luckyyulin 發布于2019-08-22 18:44 / 3387人閱讀

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

題目描述

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

分析

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

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

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

代碼實現

/*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云服務器二叉樹求結點個數二叉樹遍歷二叉樹的遍歷 JS二叉樹遍歷

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/96154.html

數據結構與算法（樹） --javascript語言描述

摘要：重建二叉樹輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。所以先通過前序遍歷找出根節點，然后將中序遍歷分為左右子樹兩組，最后對于每個子樹依次遞歸調用。重建二叉樹輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字。例如輸入前序遍歷序列{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、基礎框架3、原題鏈接二、解題報告1、思路分析2、時間復雜度3、代碼詳解三、本題小知識四、加群須知一、題目 1、題目描述 ??給你一棵二叉搜索樹，請按中序遍歷將其重新排列為一棵遞增順序搜索樹，使樹中最左邊的節點成為樹的根節點，并且每個節點沒有左子節點，只有一個右子節點。??樣例輸入： [5,3,6,2,4,null,8,1,null,null,nu...

Soarkey 2021-09-10 10:51 評論0 收藏0
數據結構與算法:二叉樹算法

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

Little_XM 2019-08-22 11:09 評論0 收藏0
js數據結構和算法（三）二叉樹

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

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

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

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