非递归遍历二叉树Java实现 |
您所在的位置：网站首页 › java二叉树递归遍历 › 非递归遍历二叉树Java实现 |
|
题目： 要求使用非递归的方法，中序遍历二叉树。
解答：
前序遍历 可以使用一个栈来模拟这种操作： 首先将root压栈； 每次从堆栈中弹出栈顶元素，表示当前访问的元素，对其进行打印； 依次判断其右子树，左子树是否非空，并进行压栈操作，至于为什么先压栈右子树，因为先压栈的后弹出，左子树需要先访问，因此后压栈； 中序遍历和后序遍历复杂一些。 1 public class Solution { 2 3 // 非递归前序遍历 4 public List preorderTraversal(TreeNode root) { 5 List res = new ArrayList(); 6 if(root == null) { 7 return res; 8 } 9 10 Stack stack = new Stack(); 11 stack.push(root); 12 13 while(!stack.isEmpty()) { 14 TreeNode current = stack.pop(); 15 res.add(current.val); 16 17 if(current.right != null) { 18 stack.push(current.right); 19 } 20 21 if(current.left != null) { 22 stack.push(current.left); 23 } 24 } 25 26 return res; 27 } 28 29 // 非递归中序遍历 30 public List inorderTraversal(TreeNode root) { 31 List res = new ArrayList(); 32 IF(root == null) { 33 return res; 34 } 35 36 Stack stack = new Stack(); 37 38 TreeNode p = root; 39 while(p != null || !stack.isEmpty()) { 40 if(p != null) { 41 stack.push(p); 42 p = p.left; 43 } else { 44 p = stack.pop(); 45 res.add(p.val); 46 p = p.right; 47 } 48 } 49 50 return res; 51 } 52 53 // 非递归后序遍历 54 public List postorderTraversal(TreeNode root) { 55 List res = new ArrayList(); 56 if(root == null) { 57 return res; 58 } 59 60 Stack stack = new Stack(); 61 62 TreeNode p = root; 63 64 // 标记最近出栈的节点，用于判断是否是p节点的右孩子，如果是的话，就可以访问p节点 65 TreeNode pre = p; 66 67 while(p != null || !stack.isEmpty()) { 68 if(p != null) { 69 70 stack.push(p); 71 p = p.left; 72 73 } else { 74 p = stack.pop(); 75 76 if(p.right == null || p.right == pre) { 77 res.add(p.val); 78 pre = cur; 79 p = null; 80 } else { 81 stack.push(p); 82 p = p.right; 83 stack.push(p); 84 p = p.left; 85 } 86 } 87 } 88 89 return res; 90 } 91 92 // 非递归层次遍历 93 public List levelTraversal(TreeNode root) { 94 List res = new ArrayList(); 95 if(root == null) { 96 return res; 97 } 98 99 Queue queue = new LinkedList(); 100 101 q.add(root); 102 103 while(!queue.isEmpty()) { 104 // current node 105 TreeNode current = queue.remove(); 106 res.add(current.val); 107 108 if(current.left != null) { 109 queue.add(current.left); 110 } 111 112 if(current.right != null) { 113 queue.add(current.right); 114 } 115 } 116 117 return res; 118 } 119 120 121 }
|
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |