转载

关于Leetcode上二叉树的算法总结

二叉树，结构很简单，只是比单链表复杂了那么一丢丢而已。我们先来看看它们结点上的差异：

/* 单链表的结构 */ 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;  } };