leetcode

特點(diǎn)1 雖然是從root開始，但是 嚴(yán)重依賴從下到上的反饋的數(shù)據(jù) ，例如求tree的高度

題目1 最近公共祖先(LCA)

給定一個(gè)二叉樹, 找到該樹中兩個(gè)指定節(jié)點(diǎn)的最近公共祖先。

百度百科中最近公共祖先的定義為：“對(duì)于有根樹 T 的兩個(gè)結(jié)點(diǎn) p、q，最近公共祖先表示為一個(gè)結(jié)點(diǎn) x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大(一個(gè)節(jié)點(diǎn)也可以是它自己的祖先)。”

LCA 2和5 返回52次

8和7 從上到下不知道，在返回過(guò)程中才知道

公共節(jié)點(diǎn)

code

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root ==NULL) { return root; } if(root ==p || root ==q) { return root; } TreeNode* left =lowestCommonAncestor(root->left,p,q); TreeNode* right=lowestCommonAncestor(root->right,p,q); if(left && right) { return root; } //如果都不是返回都不是，如果其中一個(gè)是返回其中一個(gè)。 //如果2個(gè)都是，肯定不進(jìn)入到這里 方向的選擇一個(gè)就可以 return left ?left:right; }};

---

題目2 LeetCode 110. Balanced Binary Tree

依賴下面反饋

• 文字描述

遞歸入棧過(guò)程中，是不知道是否滿足條件的。

只有出棧時(shí)候依賴下面反饋

這里 同時(shí)統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)的高度 和是否平衡

而不是從root節(jié)點(diǎn)開始判斷 是否平衡。

• 代碼實(shí)現(xiàn)

遞歸遍歷，依賴下面數(shù)據(jù)

合并在一起

特點(diǎn)2 從上到下，依賴當(dāng)前root節(jié)點(diǎn)判斷

---

1 翻轉(zhuǎn)等價(jià)二叉樹

我們可以為二叉樹 T 定義一個(gè)翻轉(zhuǎn)操作，如下所示：選擇任意節(jié)點(diǎn)，然后交換它的左子樹和右子樹。

只要經(jīng)過(guò)一定次數(shù)的翻轉(zhuǎn)操作后，能使 X 等于 Y，我們就稱二叉樹 X 翻轉(zhuǎn)等價(jià)于二叉樹 Y。

編寫一個(gè)判斷兩個(gè)二叉樹是否是翻轉(zhuǎn)等價(jià)的函數(shù)。這些樹由根節(jié)點(diǎn) root1 和 root2 給出

• 選擇任意節(jié)點(diǎn)，然后交換它的左子樹和右子樹
• 左子樹和右子樹是否繼續(xù)交換呢？ 是否選擇了任意節(jié)點(diǎn)？
• 等價(jià)tree和翻轉(zhuǎn)等級(jí)tree的結(jié)合

測(cè)試

題目理解錯(cuò)誤，以為是全部都翻轉(zhuǎn)了

code

執(zhí)行用時(shí) : 12 ms/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: bool flipEquiv(TreeNode* root1, TreeNode* root2) { if(root1 ==NULL && root2 ==NULL) { return true; } if((root1!=NULL && root2==NULL) ||(root2!=NULL &&root1==NULL)||root1->val !=root2->val) { return false; } /** if(root1->left !=root2->right ||root1->right !=root2->left) { return false; }**/ return flipEquiv(root1->left,root2->right) && flipEquiv(root1->right,root2->left) || flipEquiv(root1->left,root2->left) && flipEquiv(root1->right,root2->right); }};func flipEquiv(root1, root2 *TreeNode) bool { if root1 == nil && root2 == nil { return true } if (root1 != nil && root2 == nil) || (root1 == nil && root2 != nil) || root1.Val != root2.Val { return false } if (flipEquiv(root1.Left, root2.Left) && flipEquiv(root1.Right, root2.Right)) || (flipEquiv(root1.Left, root2.Right) && flipEquiv(root1.Right, root2.Left)) { return true } return false}

---

2 Leetcode 226： 翻轉(zhuǎn)二叉樹

翻轉(zhuǎn)一棵二叉樹

翻轉(zhuǎn)一棵二叉樹

備注:

這個(gè)問(wèn)題是受到 Max Howell 的 原問(wèn)題 啟發(fā)的 ：

谷歌：我們90％的工程師使用您編寫的軟件(Homebrew)，但是您卻無(wú)法在面試時(shí)在白板上寫出翻轉(zhuǎn)二叉樹這道題，這太糟糕了。

題目理解

潛臺(tái)詞：

一上來(lái)不要被題目嚇住，考慮到每層都要翻轉(zhuǎn) ，多么麻煩

這一次和下一層 保持左右轉(zhuǎn)換。沒(méi)有理解遞歸真正含義

從上到下遍歷過(guò)程中 來(lái)傳遞數(shù)據(jù)。

從上到下遞歸遍歷：

• root保持不變
• 左右子樹交換

• 重復(fù)步驟1和2

測(cè)試

感覺(jué)很簡(jiǎn)單呀,swap

翻轉(zhuǎn)一棵二叉樹

code

class Solution {public: TreeNode* invertTree(TreeNode* root) { if(root == NULL) { return root; } //!!!!! swap TreeNode *temp=root->left; root->left =root->right; root->right=temp; invertTree(root->left); invertTree(root->right); return root; }};

golang

func invertTree(root *TreeNode) *TreeNode {

if root ==nil {

return root

}

//golang 語(yǔ)法就是簡(jiǎn)潔

root.Left,root.Right=root.Right,root.Left

invertTree(root.Left)

invertTree(root.Right)

return root

}

總結(jié)

這幾個(gè)題目關(guān)鍵 如何理解題意 翻轉(zhuǎn)一棵二叉樹，最近公共祖先(LCA)

等等 把復(fù)雜問(wèn)題 變成重復(fù)的子問(wèn)題

• 最近公共祖先(LCA)子問(wèn)題是什么

如果當(dāng)前節(jié)點(diǎn)如果存在，左右子樹是 輸入的結(jié)果， 當(dāng)前節(jié)點(diǎn)就結(jié)果，

如果不是，返回其中任何一個(gè)可能，存在一個(gè)，或者不存在

返回不同可能就是子問(wèn)題

• 翻轉(zhuǎn)一棵二叉樹 子問(wèn)題是什么

swap(root) 不考慮層次問(wèn)題

總結(jié)

以上是生活随笔為你收集整理的source tree 递归子模块_每日刷题3--漫谈二叉树的递归遍历的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。