本质上是二叉树的层次遍历,遍历层次的过程当中把next指针加上去。
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
和问题"Populating Next Right Pointers in Each Node"类似。
如果给定的树是任意的二叉树,你先前的方法还能工作吗?
笔记:
- 你只能用常量的辅助空间。
例如给定的是羡慕的二叉树,
1
/ \
2 3
/ \ \
4 5 7
当调用完你的函数后,这个树应该看起来想这样子:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
- You may only use constant extra space.
For example,
Given the following binary tree,
1
/ \
2 3
/ \ \
4 5 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
test.cpp:
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
#include <iostream>
#include <cstdio> #include <stack> #include <vector> #include "BinaryTreeWithNext.h" using namespace std; /** if(vec[0]->left != NULL)
{ vec.push_back(vec[0]->left); } if(vec[0]->right != NULL) { vec.push_back(vec[0]->right); } vec.erase(vec.begin());
count--; if(count == 0) // 树中结点含有分叉, ConnectTreeNodes(pNodeA1, pNodeA2, pNodeA3); connect(pNodeA1); TreeLinkNode *trav = pNodeA1; DestroyTree(pNodeA1); |
结果输出:
1
2 3
4 5 7
BinaryTreeWithNext.h:
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#ifndef _BINARY_TREE_WITH_NEXT_H_
#define _BINARY_TREE_WITH_NEXT_H_ struct TreeLinkNode TreeLinkNode *CreateBinaryTreeNode(int value); #endif /*_BINARY_TREE_WITH_NEXT_H_*/ |
BinaryTreeWithNext.cpp:
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
#include <iostream>
#include <cstdio> #include "BinaryTreeWithNext.h" using namespace std; /** return pNode; //连接结点 //打印节点内容以及左右子结点内容 if(pNode->left != NULL) if(pNode->right != NULL) printf("\n"); //前序遍历递归方法打印结点内容 if(pRoot != NULL) if(pRoot->right != NULL) void DestroyTree(TreeLinkNode *pRoot) delete pRoot; DestroyTree(pLeft); |