一篇文章教你如何用多種迭代寫法實現(xiàn)二叉樹遍歷
思想
利用棧和隊列都可以實現(xiàn)樹的迭代遍歷。遞歸的寫法將這個遍歷的過程交給系統(tǒng)的堆棧去實現(xiàn)了,所以思想都是一樣的、無非就是插入值的時機不一樣。利用棧的先進先出的特點,對于前序遍歷、我們可以先將當(dāng)前的值放進結(jié)果集中,表示的是根節(jié)點的值、然后將當(dāng)前的節(jié)點加入到棧中、當(dāng)前的節(jié)點等于自己的left、再次循環(huán)的時候、也會將left作為新的節(jié)點、直到節(jié)點為空、也就是走到了樹的最左邊、然后回退、也就是彈棧、、也可以認為回退的過程是從低向上的、具體就是讓當(dāng)前的節(jié)點等于棧彈出的right、繼續(xù)重復(fù)上面的過程,也就實現(xiàn)了樹的前序遍歷、也就是bfs.后續(xù)遍歷、中序遍歷思想也是類似的。
實現(xiàn)
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; }
總結(jié)
本篇文章就到這里了,希望能給你帶來幫助,也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!
相關(guān)文章
Java ScheduledExecutorService定時任務(wù)案例講解
這篇文章主要介紹了Java ScheduledExecutorService定時任務(wù)案例講解,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-08-08JavaWeb Spring依賴注入深入學(xué)習(xí)
這篇文章主要為大家詳細介紹了JavaWeb Spring依賴注入,深入學(xué)習(xí)Spring依賴注入,感興趣的小伙伴們可以參考一下2016-09-09java高并發(fā)InterruptedException異常引發(fā)思考
這篇文章主要為大家介紹了java高并發(fā)InterruptedException異常引發(fā)思考,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2022-08-08