Shulou(Shulou.com)06/01 Report--

This article introduces you how to expand the binary tree into a linked list, the content is very detailed, interested friends can refer to, hope to be helpful to you.

The binary tree is expanded into linked table 1, a brief description of the problem

Given a binary tree, expand it into a single linked list in place.

2, an example is briefly described, for example, a given binary tree

one

/\

2 5

/\\

3 4 6

Expand it into:

one

\

two

\

three

\

four

\

five

\

six

3, the train of thought of solving the problem

Rebuild the binary tree

4, problem solving program import java.util.LinkedList

Import java.util.List

Public class FlattenTest2 {

Public static void main (String [] args) {

TreeNode T1 = new TreeNode (1)

TreeNode T2 = new TreeNode (2)

TreeNode T3 = new TreeNode (5)

TreeNode T4 = new TreeNode (3)

TreeNode T5 = new TreeNode (4)

TreeNode T6 = new TreeNode (6)

T1.left = T2

T1.right = T3

T2.left = T4

T2.right = T5

T3.right = T6

Flatten (T1)

System.out.println ("T1 =" + T1)

}

Public static void flatten (TreeNode root) {

If (root = = null) {

Return

}

LinkedList list = new LinkedList ()

Dfs (root, list)

TreeNode head = list.removeFirst ()

Head.left = null

While (list.size () > 0) {

TreeNode tempNode = list.removeFirst ()

TempNode.left = null

Head.right = tempNode

Head = head.right

}

}

Private static void dfs (TreeNode root, List list) {

If (root = = null) {

Return

}

List.add (root)

If (root.left! = null) {

Dfs (root.left, list)

}

If (root.right! = null) {

Dfs (root.right, list)

}

}

}

On how to achieve binary tree expansion into a linked list is shared here, I hope the above content can be of some help to you, can learn more knowledge. If you think the article is good, you can share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.