非递归实现二叉树先序、中序和后序遍历

tech2024-06-11  6

1.用非递归的方式实现二叉树的先序遍历(LeetCode144):

1、申请一个栈stack,然后将头节点压入stack中。

2、从stack中弹出栈顶节点,打印,再将其右孩子节点(不为空的话)先压入stack中,最后将其左孩子节点(不为空的话)压入stack中。

3、不断重复步骤2,直到stack为空,全部过程结束。

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ import java.util.*; class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> list=new ArrayList<Integer>(); Stack<TreeNode> stack=new Stack<TreeNode>(); if (root!=null) { stack.push(root); while(!stack.empty()) { TreeNode tr=stack.pop(); list.add(tr.val); if(tr.right!=null) { stack.push(tr.right); } if(tr.left!=null) { stack.push(tr.left); } } } return list; } }

2.用非递归的方式实现二叉树的中序遍历(LeetCode94):

1、申请一个栈stack,初始时令cur=head

2、先把cur压入栈中,依次把左边界压入栈中,即不停的令cur=cur.left,重复步骤2

3、不断重复2,直到为null,从stack中弹出一个节点,记为node,打印node的值,并令cur=node.right,重复步骤2

4、当stack为空且cur为空时,整个过程停止。

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<Integer> inorderTraversal(TreeNode head) { List<Integer> list=new ArrayList<Integer>(); Stack<TreeNode> stack=new Stack<TreeNode>(); if (head!=null) { while(head!=null||!stack.empty()) { if(head!=null) { stack.push(head); head=head.left; }else { head=stack.pop(); list.add(head.val); head=head.right; } } } return list; } }

3.用非递归的方式实现二叉树的后序遍历(LeetCode145):

用非递归的方式实现后序遍历有点麻烦。

1、申请一个栈s1,然后将头节点压入栈s1中。

2、从s1中弹出的节点记为cur,然后依次将cur的左孩子节点和右孩子节点压入s1中。

3、在整个过程中,每一个从s1中弹出的节点都放进s2中。

4、不断重复步骤2和步骤3,直到s1为空,过程停止。

5、从s2中依次弹出节点并打印,打印的顺序就是后序遍历的顺序。

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<Integer> postorderTraversal(TreeNode head) { List<Integer> list=new ArrayList<Integer>(); Stack<TreeNode> stack1=new Stack<TreeNode>(); Stack<TreeNode> stack2=new Stack<TreeNode>(); if (head!=null) { stack1.push(head); while(!stack1.empty()) { head=stack1.pop(); stack2.push(head); if (head.left!=null) { stack1.push(head.left); } if (head.right!=null) { stack1.push(head.right); } } while(!stack2.empty()) { list.add(stack2.pop().val); } } return list; } }
最新回复(0)