| comments | difficulty | edit_url |
|---|---|---|
true | 简单 |
二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链表，要求值的顺序保持不变，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。
返回转换后的单向链表的头节点。
注意：本题相对原题稍作改动
示例：
输入： [4,2,5,1,3,null,6,0] 输出： [0,null,1,null,2,null,3,null,4,null,5,null,6]
提示：
- 节点数量不会超过 100000。
中序遍历过程中改变指针指向。
时间复杂度
同 897. 递增顺序查找树。
# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassSolution: defconvertBiNode(self, root: TreeNode) ->TreeNode: defdfs(root): ifrootisNone: returnnonlocalprevdfs(root.left) prev.right=rootroot.left=Noneprev=rootdfs(root.right) dummy=TreeNode(val=0, right=root) prev=dummydfs(root) returndummy.right/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */classSolution { privateTreeNodeprev; publicTreeNodeconvertBiNode(TreeNoderoot) { TreeNodedummy = newTreeNode(0, null, root); prev = dummy; dfs(root); returndummy.right; } privatevoiddfs(TreeNoderoot) { if (root == null) { return; } dfs(root.left); prev.right = root; root.left = null; prev = root; dfs(root.right); } }/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * };*/classSolution { public: TreeNode* prev; TreeNode* convertBiNode(TreeNode* root) { TreeNode* dummy = newTreeNode(0, nullptr, root); prev = dummy; dfs(root); return dummy->right; } voiddfs(TreeNode* root) { if (!root) return; dfs(root->left); prev->right = root; root->left = nullptr; prev = root; dfs(root->right); } };/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcconvertBiNode(root*TreeNode) *TreeNode { dummy:=&TreeNode{Val: 0, Right: root} prev:=dummyvardfsfunc(root*TreeNode) dfs=func(root*TreeNode) { ifroot==nil { return } dfs(root.Left) prev.Right=rootroot.Left=nilprev=rootdfs(root.Right) } dfs(root) returndummy.Right }constconvertBiNode=root=>{constdfs=root=>{if(!root){return;}dfs(root.left);prev.right=root;root.left=null;prev=root;dfs(root.right);};constdummy=newTreeNode(0);letprev=dummy;dfs(root);returndummy.right;};