1102. Invert a Binary Tree (25)

简介: #include #include #include using namespace std;vector in;struct node{ int l, r;};vector tree;void inorder(int root){ if(tree[root].
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

vector<int> in;
struct node{
    int l, r;
};
vector<node> tree;
void inorder(int root){
    if(tree[root].l == -1 && tree[root].r == -1){//递归终止条件 到达根节点
        in.push_back(root);
        return;
    }
    if(tree[root].l != -1) inorder(tree[root].l);
    in.push_back(root);
    if(tree[root].r != -1) inorder(tree[root].r);
}

int main(){
    int n, root = 0;
    cin >> n;
    tree.resize(n);
    vector<int> isRoot(n);
    for (int i = 0; i < n; i++) {
        char c1, c2;
        cin >> c1 >> c2;
        tree[i].r = (c1 == '-' ? -1 : (c1 - '0'));
        tree[i].l = (c2 == '-' ? -1 : (c2 - '0'));
        if (tree[i].l != -1) isRoot[tree[i].l] = 1;
        if (tree[i].r != -1) isRoot[tree[i].r] = 1;
    }
    for (int i = 0; i < n; i++) {
        if(isRoot[i] == 0){  root = i;  break;}
    }
    queue<int> q;
    q.push(root);
    vector<int> level;
    while (! q.empty()) {
        int node = q.front();
        q.pop();
        if (tree[node].l != -1)
            q.push(tree[node].l);
        if (tree[node].r != -1)
            q.push(tree[node].r);
        level.push_back(node);
    }
    for (int i = 0; i < n; i++) {
        printf("%d%c", level[i], i == n-1 ? '\n' : ' ');
    }
    inorder(root);
    for (int i = 0; i < n; i++) {
        printf("%d%c", in[i], i == n - 1 ? '\n' : ' ');
    }
    return 0;
}
目录
相关文章
LeetCode 110. Balanced Binary Tree
给定一颗二叉树,判断此树是不是平衡二叉树. 平衡二叉树的条件是:当前节点的左右子树高度差不超过1,且左右子树都是平衡二叉树.
64 0
LeetCode 110. Balanced Binary Tree
LeetCode 111. Minimum Depth of Binary Tree
给定一棵二叉树,返回其最短深度. 题目要求是返回一颗二叉树从根节点到到所有叶节点中,深度最小的值.
78 0
LeetCode 111. Minimum Depth of Binary Tree
LeetCode 104. Maximum Depth of Binary Tree
给定一颗二叉树,返回其最大深度. 注意:深度从1开始计数.
65 0
LeetCode 104. Maximum Depth of Binary Tree
【1102】Invert a Binary Tree (25 分)
【1102】Invert a Binary Tree (25 分) 【1102】Invert a Binary Tree (25 分)
99 0
LeetCode之Maximum Depth of Binary Tree
LeetCode之Maximum Depth of Binary Tree
99 0
|
Java
[LeetCode] Minimum Depth of Binary Tree
链接:https://leetcode.com/problems/minimum-depth-of-binary-tree/description/难度:Easy题目:111.
847 0
|
Java
[LeetCode] Maximum Depth of Binary Tree
链接:https://leetcode.com/submissions/detail/136407355/难度:Easy题目:104. Maximum Depth of Binary Tree Given a binary tree, find its maximum depth.
966 0
[LeetCode]--226. Invert Binary Tree
Invert a binary tree. 4 / \ 2 7 / \ / \ 1 3 6 9 to 4 / \ 7 2 / \ / \ 9 6 3 1 Trivia: This problem was inspired by this original twe
1121 0
|
C++
[LeetCode] Closest Binary Search Tree Value II
Problem Description: Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.
1182 0