0711学习

agile Posted on Jul 11 2023

面试 leetcode学习

-   剑指 Offer 07. 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

---
![WX20230711-1454112x.png](https://tools.nxcloud.club:12500/images/2023/07/11/WX20230711-1454112x.png)

---

```C#
private Dictionary<int, int> __inOrderIndex = new Dictionary<int, int>();
private int[] __preorder;
private int __length;

public TreeNode BuildTree(int[] preorder, int[] inorder)
{
    if (preorder.Length <= 0)
    {
        return null;
    }

__length = inorder.Length;
    for (var i = 0; i < __length; i++)
    {
        __inOrderIndex[inorder[i]] = i;
    }

__preorder = preorder;
    return __BuildTree(0, 0, __length);
}

//[1,2,4,0,5,8,9,3,6] 前序遍历
//[0,4,2,8,5,9,1,3,6] 中序遍历
//前序遍历第一个肯定是root节点
//可以在中序遍历中找到该root节点，该节点左边肯定是左子树，右边肯定是右子树
//迭代就能创建一颗完整大树
// 只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。
// 由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，
// 因此我们就可以对应到前序遍历的结果中，对上述形式中的所有左右括号进行定位。
//
// 这样以来，我们就知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，
// 我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置

private TreeNode __BuildTree(int preorderIndex, int startInOrderIndex, int num)
{
    if (num == 0)
    {
        return null;
    }

var top = __preorder[preorderIndex];
    var treeNode = new TreeNode(top);
    if (num == 1)
    {
        return treeNode;
    }

var orderIndex = __inOrderIndex[top]; //在中序遍历大顺序
    var leftNum = orderIndex - startInOrderIndex; //中序遍历左边的就是左子树大数量
    var rightNum = num - leftNum - 1; //对应的就是右子数数量
    if (leftNum > 0)
    {
        treeNode.left = __BuildTree(preorderIndex + 1, startInOrderIndex, leftNum);
    }

if (rightNum > 0)
    {
        treeNode.right = __BuildTree(preorderIndex + 1 + leftNum, orderIndex + 1, rightNum);
    }

return treeNode;
}

// 迭代法的本质是若这颗树是一颗只有左子树的树,相当于一条单链表 那中序遍历和先序遍历的结果是反过来的 
// 利用栈来逆序存放 一旦遍历到最左下的地方 就开始弹出栈 若过程中栈顶弹出的和中序遍历从左往右的不想等 
// 则说明不是单链表而是多了个右孩子插在了最后一个弹出的结点的右边
public TreeNode BuildTree2(int[] preorder, int[] inorder)
{
    if (preorder.Length <= 0)
    {
        return null;
    }

var rootTree = new TreeNode(preorder[0]);
    var inOrderIndex = 0;
    var stack = new Stack<TreeNode>();
    stack.Push(rootTree);
    for (int i = 1; i < preorder.Length; i++)
    {
        var preValue = preorder[i];
        var node = stack.Peek();
        if (node.val != inorder[inOrderIndex])
        {
            node.left = new TreeNode(preValue);
            stack.Push(node.left);
        }
        else
        {
            while (stack.Count > 0 && stack.Peek().val == inorder[inOrderIndex])
            {
                node = stack.Pop();
                inOrderIndex++;
            }

node.right = new TreeNode(preValue);
            stack.Push(node.right);
        }
    }

return rootTree;
}
```

-   前序中序数组，还原出后序数组，不能创建二叉树

---

```C#
public int[] PostOrder(int[] preorder, int[] inorder)
{
    __length = preorder.Length;
    for (int i = 0; i < __length; i++)
    {
        __inOrderIndex[inorder[i]] = i;
    }

__preorder = preorder;
    var postorder = new int[__length];

__RestorePostOrder(postorder, 0, 0, __length - 1, __length);
    return postorder;
}

private void __RestorePostOrder(int[] postOrder, int preOrderIndex, int inOrderIndex, int postOrderIndex, int num)
{
    if (num == 0)
    {
        return;
    }

var currentValue = __preorder[preOrderIndex];
    var currentInOrderIndex = __inOrderIndex[currentValue];
    var leftNum = currentInOrderIndex - inOrderIndex;
    var rightNum = num - 1 - leftNum;
    postOrder[postOrderIndex] = currentValue;
    if (leftNum > 0)
    {
        __RestorePostOrder(postOrder, preOrderIndex + 1, inOrderIndex, postOrderIndex - rightNum - 1, leftNum);
    }

if (rightNum > 0)
    {
        __RestorePostOrder(postOrder, preOrderIndex + 1 + leftNum, currentInOrderIndex + 1,
            postOrderIndex - 1,
            rightNum);
    }
}
```

---

-   中序后序重建二叉树

---
```C#
private Dictionary<int, int> _cache = new Dictionary<int, int>();
private int[] _postorder;

public TreeNode BuildTree(int[] inorder, int[] postorder)
{
    _postorder = new int[inorder.Length];
    for (var i = 0; i < inorder.Length; i++)
    {
        _cache[inorder[i]] = i;
        _postorder[inorder.Length - 1 - i] = postorder[i];
    }

return __Help(0, 0, inorder.Length);
}

private TreeNode __Help(int postOrderIndex, int inOrderStartIndex, int num)
{
    if (num == 0)
    {
        return null;
    }

var value = _postorder[postOrderIndex];
    var node = new TreeNode(value);
    if (num == 1)
    {
        return node;
    }

var valueIndex = _cache[value];
    var leftNum = valueIndex - inOrderStartIndex;
    var rightNum = num - leftNum - 1;
    if (rightNum > 0)
    {
        node.right = __Help(postOrderIndex + 1, valueIndex + 1, rightNum);
    }

if (leftNum > 0)
    {
        node.left = __Help(postOrderIndex + 1 + rightNum, inOrderStartIndex, leftNum);
    }

return node;
}

public TreeNode BuildTree2(int[] inorder, int[] postorder)
{
    if (inorder.Length <= 0)
    {
        return null;
    }

var inOrderIndex = inorder.Length - 1;
    var stack = new Stack<TreeNode>();
    var rootNode = new TreeNode(postorder[inorder.Length - 1]);
    stack.Push(rootNode);
    for (int i = inorder.Length - 2; i >= 0; i--)
    {
        var node = stack.Peek();
        if (inorder[inOrderIndex] != node.val)
        {
            node.right = new TreeNode(postorder[i]);
            stack.Push(node.right);
        }
        else
        {
            while (stack.Count > 0 && inOrderIndex >= 0 && inorder[inOrderIndex] == stack.Peek().val)
            {
                node = stack.Pop();
                inOrderIndex--;
            }

node.left = new TreeNode(postorder[i]);
            stack.Push(node.left);
        }
    }

return rootNode;
}
```

---

-   剑指 Offer 16. 数值的整数次方
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，x(n)）。不得使用库函数，同时不需要考虑大数问题。
提示：
-100.0 < x < 100.0
-2(31) <= n <= 2(31)-1
n 是一个整数
要么 x 不为零，要么 n > 0 。
-10(4) <= x(n_ <= 10(4)

```C#
public double MyPow(double x, int n)
{
    if (x == 0)
    {
        return 0;
    }

if (n == 0)
    {
        return 1;
    }

// -231 <= n <= 231-1
    double extraX = 1.0f;
    if (n < 0)
    {
        x = 1 / x;
        if (n == int.MinValue)
        {
            extraX = x;
            n = int.MaxValue;
        }
        else
        {
            n = -n;
        }
    }

if (n == 1)
    {
        return x;
    }

double sum = 1;

// var binary = Convert.ToString(n, 2);
    // for (int i = binary.Length - 1; i >= 0; i--)
    // {
    //     if (binary[i] == '1')
    //     {
    //         sum *= x;
    //     }
    //
    //     x *= x;
    // }

while (n > 0)
    {
        // (n&1) 与操作 ,判断n二进制最右一位是否为 1
        if ((n & 1) == 1)
        {
            sum *= x;
        }

x *= x;
        n >>= 1;
    }

return extraX * sum;
}

public double MyPow2(double x, int n)
{
    if (x == 0)
    {
        return 0;
    }

if (n == 0)
    {
        return 1;
    }

if (n == 1)
    {
        return x;
    }

return extraX * __Dfs(x, n);
}

private double __Dfs(double x, int n)
{
    if (n == 0)
    {
        return 1;
    }

double result = 1;
    if ((n & 1) == 1)
    {
        result *= x;
    }

result *= __Dfs(x * x, n >> 1);
    return result;
}
```

-   剑指 Offer 33. 二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

![WX20230711-1912342x.png](https://tools.nxcloud.club:12500/images/2023/07/11/WX20230711-1912342x.png)
![WX20230711-1913262x.png](https://tools.nxcloud.club:12500/images/2023/07/11/WX20230711-1913262x.png)

---

```C#
//5，13，19，15，20，30，25，18，10
//先插入10
//接着可以插入18,在10打右侧（18，10）
//截止25，在18右侧（25，18，10)
//接着30，在25右侧(30,25,18,10)
//退栈30，25，记录下当前退出最大值为25，同时插入20，在25左侧 (20,18,10)
//退栈20，18，记录下当前退出最大值为18，同事插入15，在18左侧 (15,10)
//插入19，发现比最大值还大

public bool VerifyPostorder(int[] postorder)
{
    if (postorder.Length <= 2)
    {
        return true;
    }

var stack = new Stack<int>();
    var root = int.MaxValue;
    for (int i = postorder.Length - 1; i >= 0; i--)
    {
        if (postorder[i] > root)
        {
            return false;
        }

while (stack.Count > 0 && stack.Peek() > postorder[i])
        {
            root = stack.Pop();
        }

stack.Push(postorder[i]);
    }

return true;
}

public bool VerifyPostorder2(int[] postorder)
{
    return __Help(postorder, 0, postorder.Length - 1);
}

private bool __Help(int[] postorder, int i, int j)
{
    if (i >= j)
    {
        return true;
    }

var p = i;
    while (postorder[p] < postorder[j])
    {
        p++;
    }

var m = p;
    while (postorder[p] > postorder[j])
    {
        p++;
    }

return p == j && __Help(postorder, i, m - 1) && __Help(postorder, m, j - 1);
}
```