二叉樹：找到中序遍歷的下一個節點

來自專欄數據機構與演算法——雜記

思路：首先知道中序遍歷的規則是：左根右，然後作圖

【參考自牛客平評論區】

結合圖，我們可發現分成兩大類：1、有右子樹的，那麼下個結點就是右子樹最左邊的點；（eg：D，B，E，A，C，G） 2、沒有右子樹的，也可以分成兩類，a)是父節點左孩子（eg：N，I，L） ，那麼父節點就是下一個節點 ； b)是父節點的右孩子（eg：H，J，K，M）找他的父節點的父節點的父節點...直到當前結點是其父節點的左孩子位置。如果沒有eg：M，那麼他就是尾節點。

/*public class TreeLinkNode { int val; TreeLinkNode left = null; TreeLinkNode right = null; TreeLinkNode next = null; TreeLinkNode(int val) { this.val = val; }}*/public class Solution { public TreeLinkNode GetNext(TreeLinkNode pNode) { if(pNode == null)return null; if(pNode.right != null){ pNode = pNode.right; while(pNode.left != null)pNode = pNode.left; return pNode; } while(pNode.next != null){ if(pNode.next.left == pNode)return pNode.next; pNode = pNode.next; } return null; }}

推薦閱讀：