LeetCode如何實現(xiàn)二叉搜索樹與雙向鏈表

這篇文章主要介紹了LeetCode如何實現(xiàn)二叉搜索樹與雙向鏈表，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

題目

輸入一棵二叉搜索樹，將該二叉搜索樹轉(zhuǎn)換成一個排序的雙向鏈表。要求不能創(chuàng)建任何新的節(jié)點，只能調(diào)整樹中節(jié)點指針的指向。比如，輸入下圖中的二叉搜索樹，輸出轉(zhuǎn)換之后的排序雙向鏈表。

二叉樹節(jié)點的定義如下：

public static class TreeNode {
	public int val;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int x) { val = x; }
}

分析

眾所周知，中序遍歷二叉搜索樹會得到有序的序列，我們目標是在中序遍歷二叉搜索樹過程中，逐步將其轉(zhuǎn)換成有序的雙向鏈表。另外，將樹節(jié)點的左子樹指針轉(zhuǎn)換成雙向鏈表節(jié)點的前驅(qū)指針，而樹節(jié)點的右子樹指針轉(zhuǎn)換成雙向鏈表節(jié)點的后驅(qū)指針。

放碼

import com.lun.util.BinaryTree.TreeNode;

public class ConvertBSTToLinkedList {

	private TreeNode last;//用于指向雙向鏈表的尾節(jié)點
	
	public TreeNode convert(TreeNode root) {
		convertNode(root);
		
		TreeNode head = last;
		while(head != null && head.left != null) {
			head = head.left;
		}
		return head;
	}

	private void convertNode(TreeNode node) {
		
		if(node == null) {
			return;
		}
		
		TreeNode current = node;
		
		if(current.left != null) {
			convertNode(current.left);
		}
		
		current.left = last;//1.執(zhí)行到這步，左子樹已經(jīng)轉(zhuǎn)換成有序雙向鏈表
		
		if(last != null) {
			last.right = current;//2.
		}
		
		last = current;//3.current轉(zhuǎn)換成有序雙向鏈表的新尾節(jié)點
		
		if(current.right != null) {
			convertNode(current.right);
		}
	}
	
}

測試

import org.junit.Assert;
import org.junit.Test;

import com.lun.util.BinaryTree;
import com.lun.util.BinaryTree.TreeNode;

public class ConvertBSTToLinkedListTest {

	@Test
	public void test() {
		ConvertBSTToLinkedList cbl = new ConvertBSTToLinkedList();
		TreeNode root = makeABST();
		TreeNode head = cbl.convert(root);
		Assert.assertEquals("4 -> 6 -> 8 -> 10 -> 12 -> 14 -> 16 -> \n" + 
				"16 -> 14 -> 12 -> 10 -> 8 -> 6 -> 4 -> ", printList(head));
	}
	
	private TreeNode makeABST() {
		int[] array = {10, 6, 14, 4, 8, 12, 16};
		return BinaryTree.integerArray2BinarySearchTree(array);
	}
	
	private String printList(TreeNode head) {
		String result = "";
		
		TreeNode p = head;
		
		while(true) {
			result += (p.val + " -> ");
			
			if(p.right == null) {
				break;
			}
			p = p.right;
		}

		result += "\n";
		
		while(p != null) {
			result = result +  p.val + " -> ";
			p = p.left;
		}
		return result;
	}
	
}

感謝你能夠認真閱讀完這篇文章，希望小編分享的“LeetCode如何實現(xiàn)二叉搜索樹與雙向鏈表”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關(guān)注億速云行業(yè)資訊頻道，更多相關(guān)知識等著你來學(xué)習(xí)!