//二叉树自上而下 从右到左的层次遍历
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
struct TreeNode
{
char val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr){}
TreeNode(char x) : val(x), left(nullptr), right(nullptr){}
TreeNode(char x, val(x), left(left), right(right)){}
};
void invertLevelOrder( TreeNode *root)
{
queue<TreeNode*> q;
stack<TreeNode*> s;
q.push(root);
while(!q.empty())
{
TreeNode *t = q.front();
q.pop();
s.push(t);
if(t -> left) q.push(t -> left);
if(t -> right) q.push(t -> right);
}
while(s.size())
{
cout << s.top() -> val <<' ';
s.pop();
}
}
int main()
{
TreeNode *root = new TreeNode('A',new TreeNode('B', TreeNode('D'), new TreeNode('E')), new TreeNode('C'));
invertLevelOrder(root);
return 0;
}
//递归算法求二叉树高度
int height(TreeNode *root)
{
if(!root) return 0;
return max(height(root -> left), height(root -> right)) + 1;
}
//非递归求二叉树高度
//此方法也可以求每层节点个数、树的最大宽度
int height2(TreeNode *root)
{
queue<TreeNode*> q;
int height = 0;
q.push(root);
while(q.size())
{
int n = q.size();
while(n --)
{
TreeNode *t = q.front();
q.pop();
if(t -> left) q.push(t -> left);
if(t -> right) q.push(t -> right);
}
height ++;
}
return height;
}
//给定二叉树是否为完全二叉树
bool isCompleteTree(TreeNode *root)
{
queue<TreeNode*> q;
q.push(root);
bool leaf = false;
while(q.size())
{
TreeNode *t =q.front();
q.pop();
//如果已经遇到叶节点则后续所有节点都应该是叶节点不应改有孩子
//如果已经遇到叶节点且当前节点还有子节点,false
if(leaf && (t -> left || t -> right)) return false;
//若遇到叶节点
if(!t -> left && !t -> right) leaf = true;
//若左子树不空右子树空
if(!t -> left && t -> right) return false;
if(t -> left) q.push(t -> left);
if(t -> right) q.push(t -> right);
}
return true;
}
//计算双分支节点数
int res = 0;
void dfs()
{
if(!root) return ;
if(root -> left && root -> right) res ++;
dfs(root -> left);
dfs(root -> right);
}
//交换所有节点左右子树
void swapLR(TreeNode *root)
{
if(root == nullptr) return;
swap(root -> left, root -> right);
swapLR(root -> left);
swapLR(root -> right);
}
//先序遍历中第k个节点值
void dfs(TreeNode * root, int k)
{
i ++;
if(i == k) res = root -> val;
if(root -> left) dfs(root -> left);
if(root -> right) dfs(root -> right);
}
//对于每个元素值为x的元素,删去以他为根的节点
void dfs(TreeNode *root, char x)
{
if(!root) return ;
if(root -> val == x) root = NULL;
else
{
cout << root -> val << ' ';
dfs(root -> left, x);
dfs(root -> right, x);
}
}
//二叉树查找值为x的节点的所有祖先节点
//打印值为x 的 结点的所有祖先
//(查找路径) o(n)
//算法一:分别找出根节点到两个节点的路径,则最后一个公共节点就是最低公共祖先
vector<TreeNode *> findPath(TreeNode *root, TreeNode*p)
{
vector<TreeNode*>s;
TreeNode *cur = root, *pre = NULL;
while (cur || s.size())
{
while (cur)
{
s.push_back(cur);
cur = cur -> left;
}
cur = s.back();
if(cur -> right && cur -> right != pre)
cur = cur -> right;
else
{
s. pop_back();
if (cur == p)
return s;
pre = cur;
cur =NULL;
}
}
}
TreeNode* lowestCommonAncestor(TreeNode*root,TreeNode* p, TreeNode* q)
{
vector<TreeNode *> path1 = findPath(root, p);
vector<TreeNode *> path2 = findPath(root, q);
for (int i = 0; ; i ++)
if (path1[i] != path2[i])
return path1[i - 1];
return NULL;
}
//算法二:(递归) O(n)
//考虑在左子树和右子树中查找这两个节点,如果两个节点分别位于左子树和右子树,则最低公共祖先为自己(root),若左子树中两个节点都找不到,说明最低公共祖先一定在右子树中,反之亦然。考虑到二叉树的递归特性,因此可以通过递归来求得。
//时间复杂度分析:需要遍历树,复杂度为O(n)
class solution{
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if( !root)
return NULL;
if(root==p || root==q)
return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if( left&&right)
return root;
if(left==NULL)
return right;
else
return left;
}
};