思想
利用栈和队列都可以实现树的迭代遍历。递归的写法将这个遍历的过程交给系统的堆栈去实现了，所以思想都是一样的、无非就是插入值的时机不一样。利用栈的先进先出的特点，对于前序遍历、我们可以先将当前的值放进结果集中，表示的是根节点的值、然后将当前的节点加入到栈中、当前的节点等于自己的left、再次循环的时候、也会将left作为新的节点、直到节点为空、也就是走到了树的最左边、然后回退、也就是弹栈、、也可以认为回退的过程是从低向上的、具体就是让当前的节点等于栈弹出的right、继续重复上面的过程，也就实现了树的前序遍历、也就是bfs.后续遍历、中序遍历思想也是类似的。
实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 |
public List<Integer> preorderTraversal1(TreeNode root) { List<Integer> res = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); while (!stack.isEmpty() || root != null ) { while (root != null ) { res.add(root.val); stack.add(root); root = root.left; } TreeNode cur = stack.pop(); root = cur.right; } return res; } public List<Integer> preorderTraversal2(TreeNode root) { List<Integer> res = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); while (!stack.isEmpty() || root != null ) { if (root != null ) { res.add(root.val); stack.add(root); root = root.left; } else { TreeNode cur = stack.pop(); root = cur.right; } } return res; } public List<Integer> preorderTraversal3(TreeNode root) { List<Integer> res = new ArrayList<>(); if (root == null ) return res; Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode cur = stack.pop(); res.add(cur.val); if (cur.right != null ) { stack.push(cur.right); } if (cur.left != null ) { stack.push(cur.left); } } return res; } public List<Integer> preorderTraversal4(TreeNode root) { List<Integer> res = new ArrayList<>(); if (root == null ) { return res; } LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { root = queue.poll(); res.add(root.val); if (root.right != null ) { queue.addFirst(root.right); } if (root.left != null ) { root = root.left; while (root != null ) { res.add(root.val); if (root.right != null ) { queue.addFirst(root.right); } root = root.left; } } } return res; } public List<Integer> inorderTraversal1(TreeNode root) { List<Integer> res = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); while (root != null || !stack.isEmpty()) { if (root != null ) { stack.add(root); root = root.left; } else { TreeNode cur = stack.pop(); res.add(cur.val); root = cur.right; } } return res; } public List<Integer> inorderTraversal2(TreeNode root) { List<Integer> res = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); while (root != null || !stack.isEmpty()) { while (root != null ) { stack.add(root); root = root.left; } TreeNode cur = stack.pop(); res.add(cur.val); root = cur.right; } return res; } public List<Integer> postorderTraversal1(TreeNode root) { List<Integer> res = new ArrayList<>(); if (root == null ) return res; Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode cur = stack.pop(); res.add(cur.val); if (cur.left != null ) { stack.push(cur.left); } if (cur.right != null ) { stack.push(cur.right); } } Collections.reverse(res); return res; } public List<Integer> postorderTraversal2(TreeNode root) { List<Integer> res = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); while (!stack.isEmpty()) { while (root != null ) { res.add(root.val); stack.push(root); root = root.right; } TreeNode cur = stack.pop(); root = cur.left; } Collections.reverse(res); return res; } public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> ret = new ArrayList<>(); if (root == null ) return ret; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()){ int size = queue.size(); List<Integer> list = new ArrayList<>(); while (size!= 0 ){ TreeNode cur = queue.poll(); list.add(cur.val); if (cur.left!= null ){ queue.offer(cur.left); } if (cur.right!= null ){ queue.offer(cur.right); } size --; } ret.add(list); } return ret; } |
总结
本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注的更多内容！
原文链接：https://blog.csdn.net/qq_45859087/article/details/119141358
查看更多关于一篇文章教你如何用多种迭代写法实现二叉树遍历的详细内容...