程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LeetCode解題之 Recover Binary Search Tree

LeetCode解題之 Recover Binary Search Tree

編輯:關於C++

LeetCode解題之Recover Binary Search Tree


原題

一棵二叉搜索樹中的兩個節點交換了位置,找出並調整。

注意點:

最好只用常量的空間

例子:

輸入:

  3
 / \
1   2

輸出:

  2
 / \
1   3

解題思路

二叉搜索樹的中序遍歷可以使它的節點排列成一個遞增的序列,那就可以把問題簡化成在一個遞增序列中有兩個元素交換了位置。而前面的元素大於後面的元素表示順序出錯,如果整個序列就一處這樣的問題,那只要交換這兩個元素,如果有兩處,在只有兩個元素順序有問題的前提下,應該交換第一次錯位的前元素(大的元素應該往後放)與第二次錯位的後元素(小元素往前放)。

AC源碼

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution(object):
    def __init__(self):
        self.node1 = None
        self.node2 = None
        self.pre = None

    def recoverTree(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        self.__scan(root)
        self.node1.val, self.node2.val = self.node2.val, self.node1.val

    def __scan(self, root):
        if root is None:
            return
        self.__scan(root.left)
        if self.pre is not None:
            if root.val < self.pre.val:
                if self.node1 is None:
                    self.node1 = self.pre
                    self.node2 = root
                else:
                    self.node2 = root
        self.pre = root
        self.__scan(root.right)


if __name__ == "__main__":
    None
   
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved