翻轉(zhuǎn)一棵二叉樹秀撇。
示例：
輸入：
4
/ \
2 7
/ \ / \
1 3 6 9
輸出：
4
/ \
7 2
/ \ / \
9 6 3 1
備注:
這個(gè)問題是受到 Max Howell 的 原問題 啟發(fā)的 ：
谷歌：我們90％的工程師使用您編寫的軟件(Homebrew)，但是您卻無法在面試時(shí)在白板上寫出翻轉(zhuǎn)二叉樹這道題乾忱，這太糟糕了。
思路：
使用遞歸，交換當(dāng)前節(jié)點(diǎn)左右子樹，然后分別向兩個(gè)子樹遞歸
性能分析：
遍歷整棵樹徘键，時(shí)間復(fù)雜度O(N)
每層記錄一個(gè)root值，空間復(fù)雜度O(logN)
具體代碼：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null){ //空節(jié)點(diǎn)直接返回
return null;
}
//交換當(dāng)前節(jié)點(diǎn)左右子樹
TreeNode t = root.left;
root.left = root.right;
root.right = t;
//向左子樹遞歸
invertTree(root.left);
//向右子樹遞歸
invertTree(root.right);
return root;
}
}
借鑒代碼
參考資料《Leetcode 226: Invert Binary Tree(二叉樹反轉(zhuǎn) 遞歸遍蟋、非遞歸實(shí)現(xiàn))》
非常棒的寫法啊鸭，用短短幾行，實(shí)現(xiàn)了兩個(gè)功能：1匿值、交換左右子樹；2赂摆、向左右子樹遞歸
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null){ //空節(jié)點(diǎn)直接返回
return null;
}
TreeNode t = root.left;
root.left = invertTree(root.right);
root.right = invertTree(t);
return root;
}
}
