c++ 最简单的解法
二叉搜索树与双向链表
http://www.nowcoder.com/questionTerminal/947f6eb80d944a84850b0538bf0ec3a5
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: vector<TreeNode*> listnode; void dfs(TreeNode* pRootOfTree) { if(pRootOfTree!=NULL) { dfs(pRootOfTree->left); listnode.push_back(pRootOfTree); dfs(pRootOfTree->right);} } TreeNode* Convert(TreeNode* pRootOfTree) { if(pRootOfTree==NULL) return pRootOfTree; dfs(pRootOfTree); int m = listnode.size(); for(int i = 0; i<m ; i++) { if(i<m-1) listnode[i]->right = listnode[i+1]; if(i>0) listnode[i]->left = listnode[i-1]; } return listnode[0]; } };
由于二叉搜索树的特性,左子树<根<右子树,那么当我们用中序遍历时遍历的顺序会是递增的。
我们用一个vector将节点存下来,后面按照顺序调整链接即可。
这里进行遍历时要注意,节点非空再往下遍历,我一开始写的是
if(pRootOfTree->left!=NULL) dfs(pRootOfTree->left); listnode.push_back(pRootOfTree); if(pRootOfTree->right!=NULL) dfs(pRootOfTree->right);}
一直出段错误,原因是