翻轉(zhuǎn)二叉樹(shù)

翻轉(zhuǎn)一棵二叉樹(shù)。

示例：

輸入：

    4
   /   \
  2     7
 / \   / \
1   3 6   9

輸出：

    4
   /   \
  7     2
 / \   / \
9   6 3   1

思路:

1. 遍歷二叉樹(shù)中每個(gè)元素 (遍歷方法: 前序、后序、中序、層級(jí)遍歷)
2.遍歷拿到的元素 將元素的左子樹(shù) 和 右子樹(shù) 替換 

Java實(shí)現(xiàn)

public class _226_翻轉(zhuǎn)二叉樹(shù) {

    /**
     * 層序遍歷方法
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;

            if (node.left != null) {
                queue.offer(node.left);
            }

            if (node.right != null) {
                queue.offer(node.right);
            }

        }

        return root;
    }

    /**
     * 中序遍歷方法
     */
    public TreeNode invertTree3(TreeNode root) {
        if (root == null) return root;

        invertTree(root.right);
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        // root.right right  left 和 right的值已經(jīng)被調(diào)換過(guò)了
        invertTree(root.right);

        return root;
    }

    /**
     * 后序遍歷方法
     */
    public TreeNode invertTree2(TreeNode root) {
        if (root == null) return root;

        invertTree(root.left);
        invertTree(root.right);
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        return root;
    }

    /**
     * 前序遍歷方法
     */
    public TreeNode invertTree1(TreeNode root) {
        if (root == null) return root;

        invertTree(root.left);
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        // root.left 用left原因是  left 和 right的值已經(jīng)被調(diào)換過(guò)了
        invertTree(root.left);

        return root;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}

Swift實(shí)現(xiàn)

    func invertTree(_ root: TreeNode?) -> TreeNode? {
        
        if root == nil { return root }
        
        var queue = [TreeNode]();
        queue.append(root!);
        while !queue.isEmpty {
            let node = queue.popLast()
            
            let temp = node?.left
            node?.left = node?.right
            node?.right = temp
            
            if node?.left != nil {
                queue.append((node?.left)!)
            }
            if node?.right != nil {
                queue.append((node?.right)!)
            }
        }
        return root
    }


public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    
    init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}