二叉树的层序遍历:https://leetcode.cn/problems/binary-tree-level-order-traversal/
层序遍历使用队列实现:用size记录当前层的个数,size--控制弹出元素的个数,保证当前层的元素都弹出后,再去遍历弹出下一层的元素。
public List<List<Integer>> levelOrder(TreeNode root) { ArrayList<List<Integer>> res = new ArrayList<>(); if (root == null){ return res; } //借助队列 LinkedList<TreeNode> treeNodes = new LinkedList<>(); treeNodes.offer(root); while (!treeNodes.isEmpty()){ ArrayList<Integer> list = new ArrayList<>(); int size = treeNodes.size(); while (size-- > 0){//不能使用treeNodes.size()--,因为treeNodes.size()是不断变化的 TreeNode pop = treeNodes.pop(); list.add(pop.val); if (pop.left != null){ treeNodes.offer(pop.left); } if (pop.right != null) { treeNodes.offer(pop.right); } } res.add(list); } return res; }
226.反转二叉树:https://leetcode.cn/problems/invert-binary-tree/
广度优先搜索BFS:遍历每一层的时候翻转二叉树
深度优先搜索DFS:
指针交换、而不是只是交换值。前序和后序最直接。
递归遍历需要再理解理解。
class Solution{ //DFS、递归 public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } //后序遍历 invertTree(root.left); invertTree(root.right); reverseNode(root); return root; } private void reverseNode(TreeNode root) { TreeNode temp = root.left; root.left = root.right; root.right = temp; } }
标签:遍历,TreeNode,root,随想录,pop,二叉树,第十五天,treeNodes,size From: https://www.cnblogs.com/li-keke/p/16887752.html