| |
Binary Tree, the structure is very simple, just more complicated than a single list so Diudiu only. Let's take a look at the differences between them on the node:
/ * Single linked list structure * /
struct SingleList {
int element;
struct SingleList * next;
};
/ * Binary tree structure * /
struct BinaryTree {
int element;
struct BinaryTree * left;
struct BinaryTree * right;
};
According to the above two structures, we find that a single list node only a pointer to the next node, and there are two binary tree. That single list each node has only one child node, and the binary tree has two children (one of which may be NULL). Knowing this distinction, we know: based on binary tree algorithm than the algorithm based on the difference a single list is a node after each iteration, need to traverse two child nodes, but only need to traverse a single list of child nodes.
This leads to two kinds of traversal methods: breadth-first traversal (BFS) and depth-first traversal (DFS).
For a single linked list is, the BFS and DFS is the same, since each node has only one child node, each node in a next traverse only one choice; but binary tree each node has two child nodes, i.e. traversal order is either it can traverse the child nodes (node, whether left or right node are DFS), also can traverse its sibling nodes. If each time to traverse the child nodes so that DFS; the first traversing each sibling node is BFS.
DFS uses stack structure, bloggers here is the recursive stack to achieve, of course, we can also use the stack to achieve; BFS uses a queue queue.
void dfs (BinaryTree * root) {
if (NULL == root)
return;
dfs (root-> left);
dfs (root-> right);
}
void bfs (BinaryTree * root) {
if (NULL == root)
return;
queue 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);
}
}
About some algorithms tree, DFS and BFS are generally applicable, but when it comes to the root to leaf path of such problems, it is best to use DFS to achieve. As follows:
1, to a binary tree and a value Sum, all values obtained from root to leaf is equal to Sum of all paths.
Ideas: depth-first search (DFS), and then with the start of each visit from a node to put the node added to the last position of a vec, and subtract the sum is passed to the next node by value after the current point, when about a child node are NULL, and the value equal to the sum, it shows that the node is a leaf node, and from the root to the node path and the Sum, the vec, added to the res; and each return , you need to vec last value is removed, since each node has two child nodes, the path from the root to the leaves and children left the path to the right child leaves is different, all the children left after each visit or children need the right to remove the child from the value of the 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 > res;
vector 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 > pathSum (TreeNode * root, int sum) {
if (NULL == root)
return res;
_pathSum (root, sum);
return res;
}
};
2, binary conversion
The binary tree:
4
/ \
27
/ \ / \
1369
Converted to
4
/ \
72
/ \ / \
9631
Thoughts: This can either be used with the DFS BFS, which is to traverse each node, and then you can swap them around children. BFS used here to achieve:
/ **
* 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 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, summary
Once you master the DFS and BFS ideas, other algorithms on binary trees are basically similar, when necessary, by drawing to make their own perceptions of what is excellent. |
|
|
|