2023年6月22日发(作者：)

⼆叉树的遍历算法（DFS和BFS）⼆叉树的遍历算法（DFS和BFS）/* Definition for a binary tree node. */public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; }}深度优先遍历(DFS)迭代算法前序遍历（先访问根节点）⽤⼀个stack进⾏辅助class Solution { public List preorderTraversal(TreeNode root) { Deque stack = new ArrayDeque<>(); LinkedList res = new LinkedList<>(); if (root == null) { return res; } (root); while (!y()) { TreeNode node = (); (); if ( != null) { (); } if ( != null) { (); } } return res; }}中序遍历（中间访问根节点）⽤⼀个stack进⾏辅助class Solution { public List inorderTraversal(TreeNode root) { List res = new LinkedList<>(); Deque stack = new ArrayDeque<>(); if(root == null) return res; TreeNode curr = root; while(curr!=null || !y()){ while(curr != null){ (curr); curr = ; } curr = (); (); curr = ; } return res; }}后序遍历（最后访问根节点）后序遍历相较于前两种更复杂⼀些，有两种⽅法。⽅法⼀：⽤⼀个stack进⾏辅助，mark标记了上⼀个访问过的节点，在判断节点是否⼊栈时将mark作为判断条件之⼀，这样就避免了访问过的节点再次⼊栈。class Solution { public List postorderTraversal(TreeNode root) { LinkedList res = new LinkedList<>(); Deque stack = new ArrayDeque<>(); if(root == null) return res; (root); TreeNode mark = root; while(!y()){ TreeNode top = (); if( != null && != mark && != mark){ (); }else if( != null && != mark){ (); }else{ mark = (); (); }

} return res; }}⽅法⼆：⽤了两个stack进⾏辅助，思路是将待访问的节点按照逆序push进stack2，然后遍历stack2的顺序即为后续遍历的顺序。之所以能够这么做是因为我们最先访问的节点是⽗节点，这个节点在后续遍历中最后访问，我们就可以将它最先push进stack2，然后再push右⼦节点、左⼦节点。在push右⼦节点时，它本⾝也是⼀个⽗⼦节点，所以再push它的右⼦节点、左⼦节点。这种递归关系被保存在stack1中，使得节点按照顺序push进stack2中。class Solution { public List postorderTraversal(TreeNode root) { LinkedList res = new LinkedList<>(); if(root == null) return res; Deque stack1 = new ArrayDeque<>(); Deque stack2 = new ArrayDeque<>(); (root); while(!y()){ TreeNode temp = (); (temp); if( != null) (); if( != null) ();

} while(!y()){ (().val); } return res; }}递归算法递归算法⽐较简单，这⾥不再赘述迭代算法与递归算法⽐较因为每⼀个节点都要被访问，所以两种⽅法的时间复杂度都为O(N)。对于空间复杂度，递归算法的空间复杂度为O(N)，当树很⼤时，会出现stackoverflow的问题。迭代算法由于借助了stack，最坏的情况下节点全部⼊栈，因此空间复杂的也为O(N)，同样存在stackoverflow的问题。值得注意的是，有⼀种迭代算法可以将空间复杂度降低到O(1)，它就是Morris迭代算法。⼴度优先遍历(BFS)递归算法class Solution { public List> levelOrder(TreeNode root) { List> res = new ArrayList<>(); if(root == null) return res; helper(root, 0, res); return res; } public void helper(TreeNode node, int level, List> res){ if(() == level) //如果没有这⼀层，则创建它 (new ArrayList()); (level).add(); if( != null) helper(, level+1, res); if( != null) helper(, level+1, res); }}迭代算法每次迭代都创建新的⼀层，把这层上的节点（被储存在queue中）的值放进去，并按从左到右的顺序把每个节点的左右⼦节点放进queue，作为下⼀层的节点储存下来。class Solution { public List> levelOrder(TreeNode root) { List> res = new ArrayList<>(); if(root == null) return res; Queue queue = new LinkedList<>(); (root); int level = 0; while(!y()){ (new ArrayList()); int queueSize = (); for(int i = 0; i

} level++; }

return res; }}迭代算法与递归算法⽐较两种算法的时间复杂度和空间复杂度都为O(N)。