二叉树的遍历
二叉树的前序遍历(非递归)
方法一
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode *> Tree;
vector<int> ret;
while (!Tree.empty() || root != nullptr) {
while (root != nullptr) {
ret.push_back(root->val);
Tree.push(root);
root = root->left;
}
root = Tree.top();
Tree.pop();
root = root->right;
}
return ret;
}
};
方法二
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ret;
if (root == NULL) return ret;
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
TreeNode* node = s.top();
s.pop();
ret.push_back(node->val); // 记录先序遍历结果
if (node->right) s.push(node->right);
if (node->left) s.push(node->left);
}
return ret;
}
};
中序遍历(非递归)
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ret;
if (root == NULL) return ret;
stack<TreeNode*> s;
TreeNode* node = root;
// 没有压入元素或者有未弹出的元素
while (node || !s.empty()) {
// 压入左子树
while (node) {
s.push(node);
node = node->left;
}
// 弹出栈顶元素
node = s.top();
s.pop();
ret.push_back(node->val); // 记录中序遍历结果
// 进入右子树
node = node->right;
}
return ret;
}
};
中序遍历——颜色标记法
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
this.val = x;
this.left = null;
this.right = null;
}
}
class ColorNode {
TreeNode node;
String color;
ColorNode(TreeNode node, String color) {
this.node = node;
this.color = color;
}
}
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root == null) return res;
Stack<ColorNode> stack = new Stack<>();
ColorNode colorNode = new ColorNode(root, "white");
stack.push(colorNode);
while(!stack.empty()) {
colorNode = stack.pop();
if(colorNode.color.equals("white")) {
//RNL
if(colorNode.node.right != null) {
stack.push(new ColorNode(colorNode.node.right, "white"));
}
stack.push(new ColorNode(colorNode.node, "gray"));
if(colorNode.node.left != null) {
stack.push(new ColorNode(colorNode.node.left, "white"));
}
} else {
res.add(colorNode.node.val);
}
}
return res;
}
后序遍历(非递归)
方法一
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ret;
if(root == NULL) return ret;
stack<TreeNode*> s;
s.push(root);
while(!s.empty()) {
TreeNode *n = s.top();
s.pop();
ret.push_back(n->val); // 记录后续遍历的过程值
if(n->left) s.push(n->left);
if(n->right) s.push(n->right);
}
reverse(ret.begin(), ret.end()); // 将ret倒置获得后序遍历结果
return ret;
}
};
方法二
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
if(root == nullptr) return result;
stack<TreeNode*> s;
TreeNode *p = root, *r = nullptr;
while(p || !s.empty()){
while (p) {
s.push(p);
p = p->left;
}
p = s.top();
if (p->right && p->right != r) { //考虑栈顶结点的右子树结点。存在且没被访问过,将右子树结点压入栈中
p = p->right;
} else {
s.pop();
result.push_back(p->val);
r = p;
p = nullptr;
//p置空作用在于当原栈顶结点被访问并弹出后,下一层while是将当前栈顶结点的左子树入栈,当前栈顶结点的左子树已经被遍历过,
//因此会造成死循环,所以将p置空,直接考虑当前栈顶结点的右子树
}
}
return result;
}
};
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
if(root == nullptr) return result;
stack<TreeNode*> s;
TreeNode *p = root, *r = nullptr;
while(p || !s.empty()){
while (p) {
s.push(p);
p = p->left;
}
p = s.top();
if (p->right && p->right != r) {
p = p->right;
} else {
s.pop();
result.push_back(p->val);
r = p;
p = nullptr;
}
}
return result;
}
};
层序遍历
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int> > ret;
if (!root) return ret;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int count = q.size();
ret.push_back(vector<int>() );
for (int i = 1; i <= count; ++i) { // 遍历当前层所有结点,并将其孩子结点入队
TreeNode* node = q.front();
q.pop();
ret.back().push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return ret;
}
};