要將二叉樹轉換為雙向鏈表,可以使用中序遍歷來實現。具體步驟如下:
public class Node
{
public int val;
public Node prev;
public Node next;
public Node(int val)
{
this.val = val;
this.prev = null;
this.next = null;
}
}
public class TreeNode
{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val)
{
this.val = val;
this.left = null;
this.right = null;
}
}
public class Solution
{
private Node prev;
public Node Convert(TreeNode root)
{
if (root == null)
return null;
Node dummy = new Node(-1);
prev = dummy;
InOrder(root);
Node head = dummy.next;
head.prev = null;
return head;
}
private void InOrder(TreeNode node)
{
if (node == null)
return;
InOrder(node.left);
Node current = new Node(node.val);
prev.next = current;
current.prev = prev;
prev = current;
InOrder(node.right);
}
}
Convert
方法,將二叉樹轉換為雙向鏈表。class Program
{
static void Main(string[] args)
{
TreeNode root = new TreeNode(4);
root.left = new TreeNode(2);
root.right = new TreeNode(5);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(3);
Solution solution = new Solution();
Node head = solution.Convert(root);
// 遍歷雙向鏈表
Node currentNode = head;
while (currentNode != null)
{
Console.Write(currentNode.val + " ");
currentNode = currentNode.next;
}
}
}
運行上面的代碼,即可將二叉樹轉換為雙向鏈表,并輸出雙向鏈表的值。