铭记:
方式一:递归
核心思想:交换 左子树 和 右子树
/**
* 递归
*/
public TreeNode invertTree(TreeNode root) {
if (root == null) return root;
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left);
invertTree(root.right);
return root;
}
方式二:非递归
核心思路:让二叉树一一入队,然后依次从队列中取出元素,让该元素的“左子树”与“右子树”交换
public TreeNode invertTree(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode peek = queue.remove();
if (peek.left != null) {
queue.add(peek.left);
}
if (peek.right != null) {
queue.add(peek.right);
}
// 交换左右节点
TreeNode temp = peek.left;
peek.left = peek.right;
peek.right = temp;
}
return root;
}