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

LeetCode 99:Recover Binary Search Tree

編輯:關於C++

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Subscribe to see which companies asked this question

一、題目描述

一棵二叉樹原本是二叉搜索樹,但是其中有兩個節點調換了位置,要求恢復原來的二叉搜索樹

二、解題思路

中序遍歷二叉樹,出現的節點的值會升序排序,如果有兩個節點位置錯了,那肯定會出現降序。設置一個pre節點指針,記錄當前節點中序遍歷時的前節點,如果當前節點小於pre節點的值,說明需要調整次序。如果在中序遍歷時節點值出現了兩次降序,第一個錯誤的節點為第一次降序時較大的節點,第二個錯誤節點為第二次降序時較小的節點。比如,原來的搜索二叉樹在中序遍歷的節點值依次為{1,2,3,4,5},如果因為兩個節點位置錯了而出現{1,5,3,4,2},第一次降序為5->3,所以第一個錯誤節點為5,第二次降序為4->2,所以第二個錯誤節點為2,將5和2換過來就可以恢復。
//中序遍歷二叉樹,出現的節點的值會升序排序,如果有兩個節點位置錯了,那肯定會出現降序。
 //設置一個pre節點指針,記錄當前節點中序遍歷時的前節點,如果當前節點小於pre節點的值,說明需要調整次序。
 //如果在中序遍歷時節點值出現了兩次降序,第一個錯誤的節點為第一次降序時較大的節點,第二個錯誤節點為第二次降序時較小的節點。
 //比如,原來的搜索二叉樹在中序遍歷的節點值依次為{1,2,3,4,5},如果因為兩個節點位置錯了而出現{1,5,3,4,2},
 //第一次降序為5->3,所以第一個錯誤節點為5,第二次降序為4->2,所以第二個錯誤節點為2,將5和2換過來就可以恢復。
 class Solution {
 public:
	 TreeNode* mistake1;
	 TreeNode* mistake2;
	 TreeNode* pre=NULL;

	 void recoverTree(TreeNode* root) {
		 recursive_traversal(root);
		 if (mistake1 != NULL && mistake2 != NULL)
		 {
			 swap(mistake1->val, mistake2->val);
		 }
	 }

	 //遞歸中序遍歷二叉樹
	 void recursive_traversal(TreeNode* root){
		 if (root == NULL)
			 return;
		 if (root->left != NULL)
		 {
			 recursive_traversal(root->left);
		 }
		 if (pre != NULL && pre->val>root->val)
		 {
			 if (mistake1 == NULL)
			 {
				 mistake1 = pre;
				 mistake2 = root;
			 }
			 else
			 {
				 mistake2 = root;
			 }
		 }

		 pre = root;

		 if (root->right != NULL)
		 {
			 recursive_traversal(root->right);
		 }
	 }
 };

\
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved