Time:2019/4/21
Title: Invert Binary Tree
Difficulty: Easy
Author: 小鹿
題目:Invert Binary Tree(反轉(zhuǎn)二叉樹(shù))
Invert a binary tree.
反轉(zhuǎn)二叉樹(shù)
Example:
Input:
4
/ \
2 7
/ \ / \
1 3 6 9
Output:
4
/ \
7 2
/ \ / \
9 6 3 1
Solve:
▉ 問(wèn)題分析
由上圖可以分析反轉(zhuǎn)二叉樹(shù)压状,只是對(duì)左右子樹(shù)的數(shù)據(jù)進(jìn)行交換嚷量,再仔細(xì)觀察帘不,并不是每個(gè)節(jié)點(diǎn)的左右子樹(shù)進(jìn)行交換惶翻,而是左子樹(shù)的葉子節(jié)點(diǎn)和右子樹(shù)的葉子節(jié)點(diǎn)進(jìn)行交換,另外兩個(gè)子節(jié)點(diǎn)進(jìn)行交換膝蜈,那我們不得不用到遞歸了锅移。
▉ 算法思路
1)判斷樹(shù)是否為空(同時(shí)也是終止條件)。
2)左右子樹(shù)結(jié)點(diǎn)交換饱搏。
3)分別對(duì)左右子樹(shù)進(jìn)行遞歸非剃。
▉ 代碼實(shí)現(xiàn)
var invertTree = function(root) {
//判斷當(dāng)前樹(shù)是否為 null
if(root == null) return root;
//左右子樹(shù)結(jié)點(diǎn)交換
let right = root.right;
let left = root.left;
root.right = left;
root.left = right;
//分別對(duì)左右子樹(shù)進(jìn)行遞歸
invertTree(left);
invertTree(right);
//返回樹(shù)的根節(jié)點(diǎn)
return root;
};
歡迎一起加入到 LeetCode 開(kāi)源 Github 倉(cāng)庫(kù),可以向 me 提交您其他語(yǔ)言的代碼推沸。在倉(cāng)庫(kù)上堅(jiān)持和小伙伴們一起打卡备绽,共同完善我們的開(kāi)源小倉(cāng)庫(kù)!
Github:https://github.com/luxiangqiang/JS-LeetCode
歡迎關(guān)注我個(gè)人公眾號(hào):「一個(gè)不甘平凡的碼農(nóng)」坤学,記錄了自己一路自學(xué)編程的故事疯坤。