二叉树常见操作(面试)

tree.cpp

//
// Created by jvm on 4/12/19.
// Doc: https://segmentfault.com/a/1190000008850005
//

#include "tree.h"

// 求树的深度
int getDepth(Node* node) {
    if (node == nullptr) {
        return 0;
    }

    int l_depth = getDepth(node.left);
    int r_depth = getDepth(node.right);

    return l_depth > r_depth ? l_depth+1: r_depth+1
}

// 求二叉树第K层的节点个数
int getKLevel(Node *node, int k) {
    if (node == nullptr) {
        return 0;
    }

    if (k == 1) {
        return 1;
    }

    int l_KLevel = getKLevel(node->left, k-1);
    int r_KLevel = getKLevel(node->right, k-1);

    return l_KLevel + r_KLevel;
}

// 判断两颗二叉树是否结构相同
bool structureCmp(Node *node1, Node *node2) {
    if (node1 == nullptr && node2 == nullptr) {
        return true;
    }

    if (node1 == nullptr || node2 == nullptr) {
        return false
    }

    return structureCmp(node1->left, node2->left) &&
           structureCmp(node1->right, node2->right)
}

// 求二叉树的镜像
void mirror(Node* node) {
    if (node == nullptr) {
        return;
    }

    Node* tmp = node->left;
    node.left = node->right;
    node.right = tmp;

    mirror(node->left);
    mirror(node->right);
}

// 求两个节点的最低公共节点
Node* findLCA(Node *node, Node *n1, Node* n2) {
    if (node == nullptr) {
        return nullptr;
    }

    if (node == n1 && node == n2) {
        return node;
    }

    Node *left = findLCA(node->left, n1, n2);
    Node *right = findLCA(node->right, n1, n2);
    if (left && right) {
        return node;
    }

    return left ? left: right;
}

int findLevel(Node *node, Node *target) {
    if (node == nullptr) {
        return -1;
    }

    if (node == target) {
        return 0;
    }

    // 先在左子树中找
    int level = findLevel(node->left, target);
    if (level == -1) {
        // 如果左子树中没有, 在右子树中找
        level = findLevel(node->right, target);
    }

    return level == -1 ? level: level + 1
}

// 求任意两节点的距离
int distanceNodes(Node* node, Node* n1, Node* n2) {
    Node* lca = findLCA(node, n1, n2);
    int level1 = findLevel(lca, n1, n2);
    int level2 = findLevel(lca, n1, n2);

    return level1 + level2;
}

// 找出二叉树中某个节点的所有祖先节点
bool findAllAncestors(Node* node, Node* target) {
    if (node == nullptr) {
        return false;
    }

    if (node == target) {
        return true;
    }

    if (findAllAncestors(node->left, target) || findAllAncestors(node->right, target)) {
        cout << node->data << " ";
        return true; // 回溯
    }

    return false;
}

// 前序遍历(不适用递归和栈)
void preOrderTraverse(Node* root) {
    Node* cur = root;
    Node* pre = nullptr;

    while(cur) {
        if (cur->left == null) {
            cout << cur->data << " ";
            cur = cur->right;
        } else {
            pre = cur->left;
            while (pre->right && pre->right != cur) {
                pre = pre->right;
            }

            if (pre->right == nullptr) {
                cout << cur->data << " ";
                pre->right = cur;
                cur = cur->left;
            } else {
                pre->right = nullptr;
                cur = cur->right;
            }
        }
    }
}

// 前序遍历(不适用递归和栈)
void inOrderTraverse(Node* root) {
    Node* cur = root;
    Node* pre = nullptr;

    while(cur) {
        if (cur->left == nullptr) {
            cout << cur->data << " ";
            cur = cur->right;
        } else {
            pre = cur->left;
            while(pre->right && pre->right != cur) {
                pre = pre->right;
            }

            if (pre->right == nullptr) {
                pre->right = cur;
                cur = cur->left;
            } else {
                cout << cur->data << " ";
                pre->right = nullptr;
                cur = cur->right;
            }
        }
    }
}