TreeAndLinked

题目描述[原题链接][https://www.acwing.com/problem/content/description/87/]

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。

要求不能创建任何新的结点，只能调整树中结点指针的指向。

注意：

• 需要返回双向链表最左侧的节点。

例如，输入下图中左边的二叉搜索树，则输出右边的排序双向链表。

算法描述

每次从根节点开始向左右子树递归，每次返回子树最左边和最右边的节点：

• 左子树的最右边的节点的right指针指向根节点，根节点的left指针指向左子树的最右边节点
• 右子树的最左边的节点的left指针指向根节点，根节点的right指针指向左子树的最左边节点

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:
    TreeNode* convert(TreeNode* root) {
        if(!root)return NULL;
        pair<TreeNode* ,TreeNode* >p;
        p=dfs(root);
        return p.first;
    }
    
    pair<TreeNode*,TreeNode*> dfs(TreeNode* root){
        if(!root->left&&!root->right)return {root,root};
        if(root->left&&root->right){
            auto p =dfs(root->left),q=dfs(root->right);
            p.second->right=root,root->left=p.second;
            q.first->left=root,root->right=q.first;
            return {p.first,q.second};
        }
        if(root->left){
            auto p =dfs(root->left);
            p.second->right=root,root->left=p.second;
            return {p.first,root};
        }
        if(root->right){
            auto q=dfs(root->right);
            q.first->left=root,root->right=q.first;
            return {root,q.second};
        }
    }
};

Java代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode convert(TreeNode root) {
        if(root==null)return null;
        List<TreeNode> list;
        list = dfs(root);
        return list.get(0);
    }
    
    List<TreeNode> dfs(TreeNode root){
        List<TreeNode> ans = new ArrayList<>();
        if(root.left==null&&root.right==null){
            ans.add(root);
            ans.add(root);
            return ans;
        }
        if(root.left!=null&&root.right!=null){
            List<TreeNode> l1 = dfs(root.left);
            List<TreeNode> l2 = dfs(root.right);
            l1.get(1).right = root;
            root.left = l1.get(1);
            l2.get(0).left = root;
            root.right = l2.get(0);
            ans.add(l1.get(0));
            ans.add(l2.get(1));
            return ans;
        }
        if(root.left!=null){
            List<TreeNode> l1 = dfs(root.left);
            l1.get(1).right = root;
            root.left = l1.get(1);
            ans.add(l1.get(0));
            ans.add(root);
            return ans;
        }
        if(root.right!=null){
            List<TreeNode> l2 = dfs(root.right);
             l2.get(0).left = root;
            root.right = l2.get(0);
            ans.add(root);
            ans.add(l2.get(1));
            return ans;
        }
        return ans;
    }
}