Problem: 226. 翻轉二叉樹

題目描述

思路

涉及二叉樹的遞歸解法時往往需要考慮兩種思路：

1.在遞歸遍歷時執行題目需要的具體要求；
2.將一個大問題分解為多個小子問題

具體到本體：
思路1：遍歷

先序遍歷+基本的交換操作

思路2：問題分解

將翻轉一棵二叉樹分解為翻轉根節點的左右子樹，再分解為翻轉左右子樹的左右子樹…一直分解到葉子節點時，再在回退的過程中執行交換操作，即需要利用到二叉樹的后序遍歷

復雜度

思路1：
時間復雜度:

$O(n)$；其中$n$為二叉樹節點的個數

空間復雜度:

$O(n)$

思路2：
時間復雜度:

$O(n)$

空間復雜度:

$O(n)$

Code

思路1：

class Solution {/*** Invert Binary Tree(Recursive traversal)** @param root The root node of binary tree* @return TreeNode*/public TreeNode invertTree(TreeNode root) {if (root == null) {return null;}traverse(root);return root;}/*** Recursive implementation function** @param root The root node of binary tree*/private void traverse(TreeNode root) {if (root == null) {return;}TreeNode temp = root.left;root.left = root.right;root.right = temp;traverse(root.left);traverse(root.right);}
}

思路2：

class Solution {/*** Invert Binary Tree(Break down the problem)** @param root The root node of binary tree* @return TreeNode*/public TreeNode invertTree(TreeNode root) {if (root == null) {return null;}TreeNode leftNode = invertTree(root.left);TreeNode rightNode = invertTree(root.right);root.left = rightNode;root.right = leftNode;return root;}
}