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

This article shows you how to implement the non-recursive traversal of the binary tree in the Java data structure. The content is concise and easy to understand, which can definitely brighten your eyes. I hope you can get something through the detailed introduction of this article.

First, the preorder traversal 1. Topic description

Give you the root node of the binary tree, root, and return the preorder traversal of its node values.

two。 Input and output example

Example 1:

Input: root = [1flora nullpene 2pyrm 3]

Output: [1Jing 2jue 3]

Example 2:

Enter: root = []

Output: []

Example 3:

Enter: root = [1]

Output: [1]

3. Problem-solving ideas

Preorder traversal: root node-left subtree-right subtree

1. Judge the extra situation. If the tree is empty, return directly.

two。 Create a stack to hold the right subtree

3. First put the root node into the stack to avoid judging that the stack is empty many times.

4. Take out the element at the top of the stack (the root node for the first time) and traverse each node in the leftmost path from top to bottom

5. When traversing, determine whether the right subtree of the current node is empty, or enter the stack if not.

6. At the end of traversal, the top element of the stack is the right subtree of the previous node. Take out the top element of the stack, regard it as a tree, and continue to repeat the above operation, that is, to form a loop.

4. The code implements class Solution {public List preorderTraversal (TreeNode root) {List list=new ArrayList (); if (root==null) {return list;} / / creates a stack to hold the right subtree Stack s=new Stack (); TreeNode cur=root; s.push (root) / / iterate through each node in the leftmost path from top to bottom, and save its right subtree-Stack while (! s.empty () | | curvilinear null) {cur=s.pop (); while (curvilinear null) {list.add (cur.val) If (cur.rightlighting null) {s.push (cur.right);} cur=cur.left;}} return list;}} di, middle order traversal 1. Topic description

Given the root node root of a binary tree, return its mid-order traversal.

two。 Input and output example

Example 1:

Input: root = [1flora nullpene 2pyrm 3]

Output: [1, 3, 3, 2]

Example 2:

Enter: root = []

Output: []

Example 3:

Enter: root = [1]

Output: [1]

3. Problem-solving ideas

Mid-order traversal: left subtree-root node-right subtree

1. Judge the extra situation. If the tree is empty, return directly.

two。 Create a stack to hold nodes

3. Traverse each node in the leftmost path from top to bottom, save it to the stack, and go to the location of cur==null

4. The top element of the stack is the last node of the leftmost path. Add it to the list and remove the top element of the stack.

5. The process of judging whether the right subtree of the last node is empty or not is the same as the above process. The right subtree is directly regarded as a tree, and the whole process is cycled.

4. The code implements class Solution {public List inorderTraversal (TreeNode root) {List list=new ArrayList (); if (root==null) {return list;} Stack s=new Stack (); TreeNode cur=root / / iterate through each node in the leftmost path from top to bottom and save it to while (! s.empty () | curving null) {while (curving null) {s.push (cur); cur=cur.left;} cur=s.pop (); list.add (cur.val) Cur=cur.right;} return list;}} III. Traversal in post order 1. Topic description

Given a binary tree, return its post-order traversal.

two。 Input and output example

Example:

Input: [1meme nullpene 2pas 3]

one

\

two

/

three

Output: [3, 2, 2, 1]

3. Problem-solving ideas

Post-order traversal: left subtree-right subtree-root node

1. Judge the extra situation. If the tree is empty, return directly.

two。 Create a stack to hold the traversal node

3 find the leftmost node in the binary tree with cur as the root, and save all the nodes in the path-stack

4. The top element of the stack is the last node of the leftmost path.

5. First, we need to determine whether the right subtree of the last node is empty.

If empty, add the node directly to the list and delete the element at the top of the stack

If it is not empty, the right subtree is regarded as a tree and re-enters the loop judgment.

Note: if you follow this, the last right subtree will not be able to cycle out.

Solution:

Create a prev to mark the nodes that have been traversed, and change the condition for scheduling to: the right subtree of top is empty | | the right subtree of top has been traversed

4. The code implements class Solution {public List postorderTraversal (TreeNode root) {List list=new ArrayList (); if (root==null) {return list;} Stack s=new Stack (); TreeNode cur=root; TreeNode prev=null;// is used to mark the node while (! s.empty ()) that has just been traversed | | cursive null) {/ / 1. Find the leftmost node in the binary tree with cur as the root, and save all the nodes in the path-while (curvilinear null) {s.push (cur); cur=cur.left;} TreeNode top=s.peek () / / can top traverse: the right subtree of top is empty | | the right subtree of top has already traversed if (top.right==null | | top.right==prev) {list.add (top.val); prev=top; s.pop ();} else {cur=top.right;}} return list }} the above content is how to implement the non-recursive traversal of the binary tree in the Java data structure. Have you learned the knowledge or skills? If you want to learn more skills or enrich your knowledge reserve, you are welcome to follow the industry information channel.

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.