算法1
(中序遍历)
遍历过程中维护两个指针,1个指针指向现在节点,另一个指向当前节点的父指针
遍历过程中将当前节点的左子树指向父节点,将当前节点的父节点的右子树指向当前节点。
时间复杂度分析:O(N)
C++ 代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void dfs(TreeNode* c, TreeNode** la){
if (c==NULL) return;
TreeNode* k = c;
if (k->left!=NULL){
dfs(k->left,la);
}
k->left = (*la);
if((*la)!=NULL){
(*la) ->right = k;
}
(*la) = k;
if(c->right!=NULL) {
dfs(k->right,la);
}
}
TreeNode* convert(TreeNode* root) {
if (!root) return root;
TreeNode* la = NULL;
dfs(root,&la);
auto head = root;
while(head!=NULL && head->left!=NULL){
head = head->left;
}
return head;
}
};