剑指offer 二叉树 持续更新中...

1. 重建二叉树

105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

1.1 题目描述

题目描述：输入某二叉树的前序遍历和中序遍历结果，请重建二叉树。假设输入的前序遍历和中序遍历结果中不包含重复元素

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

1.2 方法1，分治

二叉树的前序遍历中：第一个数字总是树的根节点的值。当我们确立了根节点后，根据中序遍历确定左子树和右子树。一直递归下去，注意这里的区间全部是前闭后开

class Solution {
    vector<int> _preorder, _inorder;
    int _length;
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        _preorder = preorder, _inorder = inorder, _length = preorder.size();
        return buildTreeCore(0, _length, 0, _length);
    }
    TreeNode* buildTreeCore(int startPreOrder, int endPreOrder, 
                            int startInOrder, int endInorder)
    {
        if(startPreOrder >= endPreOrder || startInOrder >= endInorder) {
            return nullptr;
        }
        TreeNode* root = new TreeNode(_preorder[startPreOrder]);
        // 在中序遍历序列中找到根节点的值, 可以确定下一次左子树的长度
        int rootInOrder = startInOrder;
        while(rootInOrder < endInorder && _inorder[rootInOrder] != root->val)
            rootInOrder++;
        int leftLength = rootInOrder - startInOrder;        // 左子树的长度
        // 构建左子树
        root->left = buildTreeCore(startPreOrder+1, startPreOrder + leftLength + 1,
                                      startInOrder, rootInOrder);
        // 构建右子树
        root->right = buildTreeCore(startPreOrder + leftLength + 1, endPreOrder,
                                    rootInOrder+1, endInorder);
        return root;
    }
};

这题与之类似，106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode），都是一样的思考过程，下面是解答

class Solution {
    vector<int> _inorder, _postorder;
    int _length;

public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        _inorder = inorder, _postorder = postorder, _length = inorder.size();
        _length = inorder.size();
        return buildTreeCore(0, _length, 0, _length);
    }
    TreeNode* buildTreeCore(int startInorder, int endInorder,
                            int startPostorder, int endPostorder) {
        if (startInorder >= endInorder || startPostorder >= endPostorder)
            return nullptr;
        TreeNode* root = new TreeNode(_postorder[endPostorder - 1]);
        // 在中序序列中找到根
        int rootInorder = startInorder;
        while (rootInorder < endInorder && _inorder[rootInorder] != root->val)
            rootInorder++;
        int leftLength = rootInorder - startInorder; // 左子树的长度
        root->left = buildTreeCore(startInorder, rootInorder, startPostorder,
                                   startPostorder + leftLength);
        root->right =
            buildTreeCore(rootInorder + 1, endInorder,
                          startPostorder + leftLength, endPostorder - 1);
        return root;
    }
};

2. 二叉树的下一个节点

二叉树的下一个结点_牛客题霸_牛客网

2.1 题目描述

题目描述：给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。

示例1:

输入:{8,6,10,5,7,9,11}, 8
返回:9

2.2 方法1，模拟

1. 如果一个节点有右子树，那么它的下一个节点就是它的右子树的最左节点
2. 如果一个节点没有右子树
   1. 如果该节点是父节点的左孩子节点，那么下一个节点就是该节点的父节点
   2. 如果该节点是父节点的右孩子节点，那么就一直向上找它的父节点，直到找到一个节点，是父节点的左孩子节点，此时下一个该节点的下一个节点就是该节点的父节点。如果找到根节点了，就证明到最后了，没有下一个节点了。

class Solution 
{
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode) 
    {
        // 1.一个节点有右子树
        if(pNode->right != nullptr) {
            pNode = pNode->right;
            while(pNode->left != nullptr)
                pNode = pNode->left;
            return pNode;
        }
        auto parent = pNode->next;
        // 2.1没有右子树, 该节点是父节点的左孩子节点
        if(parent != nullptr && parent->left == pNode)
            return parent;
        // 2.2没有右子树, 该节点是父节点的右孩子节点
        while(parent != nullptr) {
            pNode = parent;
            parent = pNode->next;
            if(parent == nullptr)    break;
            if(pNode == parent->left)
                return parent;
        }
        return nullptr;
    }
};