递归:
//先序遍历
void preOrder(Node *root) {
if (root == NULL) {
return;
}
printf("%d\n", root->data);
preOrder(root->lchild);
preOrder(root->rchild);
}
//中序遍历
void inOrder(Node *root) {
if (root == NULL) {
return;
}
inOrder(root->lchild);
printf("%d\n", root->data);
inOrder(root->rchild);
}
//后序遍历
void postOrder(Node *root) {
if (root == NULL) {
return;
}
postOrder(root->lchild);
postOrder(root->rchild);
printf("%d\n", root->data);
}
//层次遍历
void levelOrder(Node *root) {
queue<Node *> q;
q.push(root);
while (!q.empty()) {
Node *now = q.front();
q.pop();
printf("%d\n", now->data);
if (now->lchild != NULL) {
q.push(now->lchild);
}
if (now->rchild != NULL) {
q.push(now->rchild);
}
}
}
非递归:
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
if (root == null) {
return null;
}
List<Integer> res = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode top = stack.poll();
res.add(top.val);
if (top.right != null) {
stack.push(top.right);
}
if (top.left != null) {
stack.push(top.left);
}
}
return res;
}
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
res.add(root.val);
root = root.right;
}
return res;
}
public List<Integer> postorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<Integer> res = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode pre = null;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (root.right == null || root.right == pre) {
res.add(root.val);
pre = root;
root = null;
} else {
stack.push(root);
root = root.right;
}
}
return res;
}
}
无论是先序遍历序列还是后序遍历序列还是层次遍历序列,都必须知道中序遍历序列才能唯一确定一棵树。
例1
给定一棵二叉树的先序遍历序列和中序遍历序列,重建这棵二叉树。
分析:

#include <cstdio>
using namespace std;
const int maxn = 100;
//二叉树存储结构
struct Node {
int data;
Node *lchild;
Node *rchild;
};
int pre[maxn], in[maxn];
Node *create(int preL, int preR, int inL, int inR) {
if (preL > preR) {
return NULL;
}
Node *root = new Node;
root->data = pre[preL];
int k;
//在中序序列中找到根结点位置
for (k = inL; k <= inR; k++) {
if (in[k] == pre[preL]) {
break;
}
}
int numLeft = k - inL;//左子树结点个数
root->lchild = create(preL + 1, preL + numLeft, inL, k - 1);
root->rchild = create(preL + numLeft + 1, preR, k + 1, inR);
return root;
}
网友评论