面试题----树
2019-08-08 本文已影响0人
世界上的一道风
94. 二叉树的非递归前序遍历
- 直接进出入栈，拿出数据：
/**
* 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:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> st;
if (!root)
return ans;
st.push(root);
while(!st.empty())
{
TreeNode *top = st.top();
ans.push_back(top->val);
st.pop();
if(top->right)
st.push(top->right);
if(top->left)
st.push(top->left);
}
return ans;
}
};
94. 二叉树的非递归中序遍历
首先是根非空入栈，对子树最左边节点一直进栈；
直到左为空，重置根为栈顶节点，取出数据并出栈；
重置根为根的右边节点；
/**
* 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:
//think:首先是根入栈，左边不为空则进栈，直到左为空出栈，然后右边不为空进栈
vector<int> inorderTraversal(TreeNode* root) {
std::stack<TreeNode *> Stack;
vector<int> ans;
while(root || !Stack.empty())
{
if (root != nullptr)
Stack.push(root);
while(root && root->left != nullptr) //先验证根是否存在；再验证左节点
{
Stack.push(root->left);
root = root->left;
}
root = Stack.top();
ans.push_back(root->val);
Stack.pop();
root = root->right;
}
return ans;
}
};
145. 二叉树的非递归后序遍历
- 跟前序遍历很像：第一次访问根节点，用于确定是否还有属于它的子节点需要进栈，若有就进栈，这是第一次遍历该节点；
不同的是：在第二次遍历时出栈。栈顶pop一个新的节点时，是第二次遍历，第二次遍历时出栈。
- 进两次栈的方法：
- 初始化：根非空进栈两次；
- 循环：栈非空的话：
* 设置当前出栈元素cur，栈顶出栈；（第一次遍历）
* 当前出栈元素等于栈顶元素（确保为第一次遍历）的话：若右非空，进栈两次，若左非空，进栈两次；否则的话（第二次遍历）：取出当前cur的值
/**
* 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:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
if(!root) return ans;
stack<TreeNode*> Stack;
TreeNode *cur;
Stack.push(root);
Stack.push(root);
while(!Stack.empty())
{
cur = Stack.top();
Stack.pop();
if(!Stack.empty() && cur==Stack.top()) //因为之前出栈，先看是否为空，然后确定目前的栈顶部节点是否访问过，如果cur与栈顶不一样，则已经访问过一次，目前这个可以出栈
{
if(cur->right) //后序遍历先进右
{
Stack.push(cur->right);
Stack.push(cur->right);
}
if (cur->left)//后进左、后进先出
{
Stack.push(cur->left);
Stack.push(cur->left);
}
}else{
ans.push_back(cur->val);
}
}
return ans;
}
};
- 考虑根节点与栈顶节点，
- 循环：若
root非空或者栈非空：
* 若根非空，进栈，设置根为根的左节点；
* 一直入栈最左的子节点（作为新根节点），直到根为空；
* 设置一个节点记录栈顶节点，若记录节点top有右节点，且最后出栈的节点不等于记录节点或栈顶节点，根节点重置为栈顶节点的右边节点；
* 否则栈顶节点无右节点，取值，出栈，重置最后出栈的节点；
/**
* 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:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
if(!root) return ans;
stack<TreeNode*> Stack;
TreeNode *last=nullptr;
while(root || !Stack.empty())
{
if(root)
{
Stack.push(root);
root = root->left;
}else{
//
TreeNode* top = Stack.top();
if (top->right && last!=top->right)
{
root = top->right;
}
else
{
ans.push_back(top->val);
last = top;
Stack.pop();
}
}
}
return ans;
}
};
- 用前序遍历，最后反转数组；
pre-order traversal is root-left-right, and post order is left-right-root. modify the code for pre-order to make it root-right-left, and then reverse the output so that we can get left-right-root
/**
* 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:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
if(!root) return ans;
stack<TreeNode*> Stack;
TreeNode *tmp;
Stack.push(root);
//前左右；左右前=前右左的反转
while(!Stack.empty())
{
tmp = Stack.top();
ans.push_back(tmp->val);
Stack.pop();
if(tmp->left)
Stack.push(tmp->left);
if(tmp->right)
Stack.push(tmp->right);
}
vector<int> rans(ans.rbegin(), ans.rend());
return rans;
}
};
98. 验证二叉搜索树
-
主要是根节点大于所有的左子树，小于所有的右子树；怎么样把这个根部的节点信息传递下去。
-
方法1：递归，除了比较根与左右节点，还要比较左右节点与上一次的根节点值是否满足大小关系；
用min判断传入为（当前根节点的）左节点时，比较右节点是否小于上一次根节点值；
用max判断传入为（当前根节点的）右节点时，比较左节点是否大于上一次根节点值；
/**
* 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:
//Thinking: 全部的子树上的节点都必须大于或者小于根节点才行
//传入子树递归的时候带上根节点的值，进行比较
bool isValidBST(TreeNode* root)
{
return _isValidBST(root, LONG_MIN, LONG_MAX);
}
bool _isValidBST(TreeNode *root,long min, long max)
{
if(!root) return true;
if(root->val<=min || root->val>=max) return false;
return (_isValidBST(root->left,min,root->val) && _isValidBST(root->right,root->val,max));
}
};
112. Path Sum
问路径上是否有简单路径和等于给定数值
/**
* 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:
bool hasPathSum(TreeNode* root, int sum) {
if(root)
{
//叶节点减为0才返回true
if (!(sum-root->val) && !root->left && !root->right)
return true;
return (hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val));
}
else
{
return 0;
}
}
};
113. Path Sum II
上一题的基础上，再加上返回所有满足这个要求的路径
- 直接类似上题解法：
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int> > paths;
vector<int> path;
findPaths(root, sum, path, paths);
return paths;
}
private:
void findPaths(TreeNode* node, int sum, vector<int>& path, vector<vector<int> >& paths) {
if (!node) return;
path.push_back(node -> val);
if (!(node -> left) && !(node -> right) && sum == node -> val)
paths.push_back(path);
findPaths(node -> left, sum - node -> val, path, paths);
findPaths(node -> right, sum - node -> val, path, paths);
path.pop_back();
}
};
