LeetCode：226翻转二叉树

方法一：递归法

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode invertTree(TreeNode root) { if(root == null){ return null; } //左右节点交换 TreeNode temp = root.right; root.right = root.left; root.left = temp; //递归左右节点 invertTree(root.left); invertTree(root.right); return root; } }

方法二：

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution{ public TreeNode invertTree(TreeNode root){ if(root == null){ return null; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ TreeNode current = queue.poll(); //交换左右节点 TreeNode temp = current.left; current.left = current.right; current.right = temp; //左右节点不为空则入队 if(current.left != null){ queue.offer(current.left); } if(current.right != null){ queue.offer(current.right); } } return root; } }

迭代法思路：

先将根节点入队

while循环，只要队列不为空就交换当前要出队节点的左右节点，然后判断当前出队节点的下面是否还有左右节点，如果有就继续入队，循环。

爆栈，层序遍历，逐层打印。寻找最短路径使用队列；核心：new Queue -> offer(root) -> while(!isEmpty) -> poll() -> 处理逻辑 -> offer(children)