LeetCode 之 JavaScript 解答第226題 —— 翻轉(zhuǎn)二叉樹（Invert Bina

MingjunYang 發(fā)布于2019-08-23 17:07 / 694人閱讀

摘要：算法思路判斷樹是否為空同時也是終止條件。分別對左右子樹進行遞歸。代碼實現(xiàn)判斷當(dāng)前樹是否為左右子樹結(jié)點交換分別對左右子樹進行遞歸返回樹的根節(jié)點歡迎一起加入到開源倉庫，可以向提交您其他語言的代碼。

Time：2019/4/21
Title: Invert Binary Tree
Difficulty: Easy
Author: 小鹿

題目：Invert Binary Tree（反轉(zhuǎn)二叉樹）

Invert a binary tree.

反轉(zhuǎn)二叉樹

Example:

Input:

     4
   /   
  2     7
 /    / 
1   3 6   9

Output:

     4
   /   
  7     2
 /    / 
9   6 3   1

Solve:

▉ 問題分析

由上圖可以分析反轉(zhuǎn)二叉樹，只是對左右子樹的數(shù)據(jù)進行交換，再仔細觀察，并不是每個節(jié)點的左右子樹進行交換，而是左子樹的葉子節(jié)點和右子樹的葉子節(jié)點進行交換，另外兩個子節(jié)點進行交換，那我們不得不用到遞歸了。

▉ 算法思路

1）判斷樹是否為空（同時也是終止條件）。

2）左右子樹結(jié)點交換。

3）分別對左右子樹進行遞歸。

▉ 代碼實現(xiàn)

var invertTree = function(root) {
    //判斷當(dāng)前樹是否為 null
    if(root == null) return root;
    //左右子樹結(jié)點交換
    let right = root.right;
    let left = root.left;
    root.right = left;
    root.left = right;
    //分別對左右子樹進行遞歸
    invertTree(left);
    invertTree(right);
    //返回樹的根節(jié)點
    return root;
};

歡迎一起加入到 LeetCode 開源 Github 倉庫，可以向 me 提交您其他語言的代碼。在倉庫上堅持和小伙伴們一起打卡，共同完善我們的開源小倉庫！
Github：https://github.com/luxiangqia...
歡迎關(guān)注我個人公眾號：「一個不甘平凡的碼農(nóng)」，記錄了自己一路自學(xué)編程的故事。