二叉樹，結構很簡單，只是比單鏈表復雜了那麼一丟丟而已。我們先來看看它們結點上的差異：
/* 單鏈表的結構 */
struct SingleList{
int element;
struct SingleList *next;
};
/* 二叉樹的結構 */
struct BinaryTree{
int element;
struct BinaryTree *left;
struct BinaryTree *right;
};
根據以上兩個結構，我們不難發現，單鏈表的結點只有一個指向下一結點的指針，而二叉樹中有兩個。也就是說單鏈表每個結點只有一個子節點，而二叉樹有兩個子節點（其中一個可能為NULL）。了解了這一點的區別，我們就知道：基於二叉樹的算法比基於單鏈表的算法差異就是每次遍歷一個結點之後，需要遍歷兩個子節點，而單鏈表只需要遍歷一個子節點。
這就引出了2種遍歷的方法：廣度優先遍歷（BFS）和深度優先遍歷（DFS）。
對於單鏈表來說，BFS和DFS是一樣的，因為每個節點只有一個子節點，每次遍歷下一個節點只有一種選擇；但是二叉樹每個節點有兩個子節點，也就是說遍歷的順序既可以遍歷它的子節點（無論左節點還是右結點都是DFS），也可以遍歷它的兄弟結點。如果是每次先遍歷子節點那麼就是DFS；每次先遍歷兄弟結點，就是BFS。
DFS采用棧結構，博主這裡用的是遞歸來實現棧，當然大家也可以用stack來實現；BFS采用的是隊列queue。
void dfs(BinaryTree *root){
if(NULL == root)
return ;
dfs(root->left);
dfs(root->right);
}
void bfs(BinaryTree *root){
if(NULL == root)
return ;
queue<BinaryTree *> que;
que.push();
while(!que.empty()){
BinaryTree *pNode = que.front();
que.pop();
if(pNode->left)
que.push(pNode->left);
if(pNode->right)
que.push(pNode->right);
}
}
關於樹的一些算法中，DFS和BFS一般都適用，但是當涉及到根到葉的路徑這類問題時，最好還是用DFS來實現。如下所示：
1、給一棵二叉樹和一個值Sum，求出所有從根到葉子的值等於Sum的所有路徑。
思路：深度優先搜索（DFS），然後把從跟開始每次訪問一個結點就把該結點添加到一個vec的最後位置，並把sum減去當前借點的值後傳遞給下一個節點，當一個結點的左右孩子都為NULL，並且值等於sum時，就說明該節點是葉子節點，並且從根結點到該節點的路徑和為Sum，把vec，添加到res中；每次返回時，需要把vec中的最後一個值刪除，因為每個節點有兩個子節點，從根節點到左孩子的葉子的路徑與到右孩子葉子的路徑是不同的，所有每次訪問完左孩子或者右孩子需要把孩子的值從vec中刪除。
/**
* 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 {
private:
vector<vector<int>> res;
vector<int> vec;
void _pathSum(TreeNode* root, int sum){
if(root == NULL)
return ;
vec.push_back(root->val);
if(root->left == NULL && root->right == NULL && sum == root->val){
res.push_back(vec);
return ;
}
_pathSum(root->left, sum-root->val);
if(root->left)
vec.pop_back();
_pathSum(root->right, sum-root->val);
if(root->right)
vec.pop_back();
}
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
if(NULL == root)
return res;
_pathSum(root, sum);
return res;
}
};
2、轉化二叉樹
把二叉樹：
4 / \ 2 7 / \ / \ 1 3 6 9
轉化成
4 / \ 7 2 / \ / \ 9 6 3 1
思路：這個既可以用DFS也可以用BFS，也就是遍歷每個節點，然後將它們的左右孩子互換即可。這裡采用BFS來實現：
/**
* 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* invertTree(TreeNode* root) {
if(NULL == root)
return NULL;
queue<TreeNode*> que;
que.push(root);
while(!que.empty()){
TreeNode* pChild = que.front();
que.pop();
TreeNode* pNode = pChild->left;
pChild->left = pChild->right;
pChild->right = pNode;
if(pChild->left)
que.push(pChild->left);
if(pChild->right)
que.push(pChild->right);
}
return root;
}
};
3、總結
只要掌握了DFS和BFS的思想，其它關於二叉樹的算法基本上都是類似的，必要的時候通過畫圖來讓自己感性認識一下也是極好的。
關於Leetcode上的題目代碼：
------------------------------------------分割線------------------------------------------
免費下載地址在 http://linux.linuxidc.com/
用戶名與密碼都是www.linuxidc.com
具體下載目錄在 /2015年資料/8月/23日/關於Leetcode上二叉樹的算法總結/
下載方法見 http://www.linuxidc.com/Linux/2013-07/87684.htm
------------------------------------------分割線------------------------------------------
