LeetCode中如何翻轉(zhuǎn)二叉樹

題目描述：

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

示例：

輸入：

 

輸出：

 

思路分析：

通過觀察，我們發(fā)現(xiàn)只要把二叉樹上的每一個節(jié)點(diǎn)的左右子節(jié)點(diǎn)進(jìn)行交換，最后的結(jié)果就是完全翻轉(zhuǎn)之后的二叉樹。

這道題目比較簡單，關(guān)鍵思路在于我們發(fā)現(xiàn)翻轉(zhuǎn)整棵樹就是交換每個節(jié)點(diǎn)的左右子節(jié)點(diǎn)，于是我們把交換左右子節(jié)點(diǎn)的代碼放在了前序遍歷的位置。

值得一提的是，如果把交換左右子節(jié)點(diǎn)的代碼放在后序遍歷的位置也是可以的，但是放在中序遍歷的位置是不行的。

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

/**
 * 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 tmp=root.left;
        root.left=root.right;
        root.right=tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

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

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return root
        
        left = self.invertTree(root.left)
        right = self.invertTree(root.right)
        root.left, root.right = right, left
        return root