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