聊聊二叉樹的左右子樹交換
作者： sisterAn
二叉樹（Binary tree）是樹形結(jié)構(gòu)的一個(gè)重要類型。許多實(shí)際問題抽象出來的數(shù)據(jù)結(jié)構(gòu)往往是二叉樹形式，即使是一般的樹也能簡(jiǎn)單地轉(zhuǎn)換為二叉樹，而且二叉樹的存儲(chǔ)結(jié)構(gòu)及其算法都較為簡(jiǎn)單，因此二叉樹顯得特別重要。
本文轉(zhuǎn)載自微信公眾號(hào)「三分鐘學(xué)前端」，作者sisterAn。轉(zhuǎn)載本文請(qǐng)聯(lián)系三分鐘學(xué)前端公眾號(hào)。
翻轉(zhuǎn)一棵二叉樹。
示例：
輸入：
- 4
- / \
- 2 7
- / \ / \
- 1 3 6 9
輸出：
- 4
- / \
- 7 2
- / \ / \
- 9 6 3 1
遍歷+交換左右子樹
解題思路： 從根節(jié)點(diǎn)開始依次遍歷每個(gè)節(jié)點(diǎn)，然后交換左右子樹既可
- const invertTree = (root) => {
- if(!root) return null
- // 先翻轉(zhuǎn)當(dāng)前節(jié)點(diǎn)的左右子樹
- const temp = root.left
- root.left = root.right
- root.right = temp
- // 然后遍歷左子樹
- invertTree(root.left)
- // 再遍歷右子樹
- invertTree(root.right)
- return root
- }
這里采用的是前序遍歷，也可以是后序遍歷或?qū)有虮闅v
leetcode：https://leetcode-cn.com/problems/invert-binary-tree
責(zé)任編輯：武曉燕
來源：
三分鐘學(xué)前端
