day20 leetcode-hot100-38（二叉树3）

226. 翻转二叉树 - 力扣（LeetCode）

1.广度遍历

思路

这题目很简单，就是交换每个节点的左右子树，也就是相当于遍历到某个节点，然后交换子节点即可。

具体步骤

（1）创建队列，使用广度优先遍历。

（2）while循环判断当前队列是否为空，不为空，就将最前面的节点poll()，然后将该节点左右子节点加入队列（广度遍历的方案），再交换左右节点。

具体代码

/*** 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 root;}TreeNode ans = root;Deque<TreeNode>dq = new LinkedList<>();dq.offer(root);while(!dq.isEmpty()){TreeNode node = dq.poll();if(node.left!=null){dq.offer(node.left);}if(node.right!=null){dq.offer(node.right);}TreeNode temp = new TreeNode();temp=node.left;node.left = node.right;node.right=temp;}return ans;}
}

2深度优先遍历（前序遍历）

思路

与上面广度优先遍历一样，也是遍历到哪个节点，然后将该节点入栈，之后交换位置。