0614学习

agile Posted on Jun 20 2023

面试 leetcode学习

---

- 交替合并字符串

给你两个字符串 word1 和 word2 。请你从 word1 开始，通过交替添加字母来合并字符串。如果一个字符串比另一个字符串长，就将多出来的字母追加到合并后字符串的末尾。

返回 合并后的字符串 。

```C#
public string MergeAlternately(string word1, string word2)
{
    var wordLength1 = word1.Length;
    var wordLength2 = word2.Length;
    var wordIndex1 = 0;
    var wordIndex2 = 0;
    var sb = new StringBuilder();
    for (var i = 0; i < wordLength1 + wordLength2; i++)
    {
        var isWord1 = i % 2 == 0;
        if (wordIndex1 < wordLength1 && wordIndex2 < wordLength2)
        {
            sb.Append(isWord1 ? word1[wordIndex1++] : word2[wordIndex2++]);
        }

if (isWord1)
        {
            if (wordIndex1 < wordLength1) continue;
            sb.Append(word2[wordIndex2..]);
            break;
        }
        else
        {
            if (wordIndex2 < wordLength2) continue;
            sb.Append(word1[wordIndex1..]);
            break;
        }
    }

return sb.ToString();
}
```

---

- 二叉树的最大深度-104

给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

```C#
public int MaxDepth(TreeNode root)
{
    if (root == null) return 0;
    var depthLeft = MaxDepth(root.left) + 1;
    var depthRight = MaxDepth(root.right) + 1;
    return Math.Max(depthLeft, depthRight);
}
```

广度搜索实现
```C#
public int MaxDepthBfs(TreeNode root)
{
    if (root == null)
    {
        return 0;
    }

var queue = new Queue<TreeNode>();
    queue.Enqueue(root);
    var depth = 0;
    while (queue.Count > 0)
    {
        var size = queue.Count;
        for (var i = 0; i < size; i++)
        {
            var t = queue.Dequeue();
            if (t.left != null)
            {
                queue.Enqueue(t.left);
            }

if (t.right != null)
            {
                queue.Enqueue(t.right);
            }
        }

depth++;
    }

return depth;
}
```

---

-   二叉树的右视图-199

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

```C#
public IList<int> RightSideView(TreeNode root)
{
    var result = new List<int>();
    if (root != null)
    {
        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        while (queue.Count > 0)
        {
            var size = queue.Count;
            for (var i = 0; i < size; i++)
            {
                var t = queue.Dequeue();
                if (t.left != null)
                {
                    queue.Enqueue(t.left);
                }

if (t.right != null)
                {
                    queue.Enqueue(t.right);
                }

if (i == size - 1)
                {
                    result.Add(t.val);
                }
            }
        }
    }

return result;
}
```
---

通过深度搜索实现
```C#
public List<int> RightSideViewDfs(TreeNode root)
{
    var result = new List<int>();
    __DfsSearch(result, root, 0);
    return result;
}

private void __DfsSearch(List<int> result, TreeNode node, int depth)
{
    if (node == null)
    {
        return;
    }

if (depth == result.Count)
    {
        result[depth] = node.val;
    }

depth++;
    __DfsSearch(result, node.right, depth);
    __DfsSearch(result, node.left, depth);
}
```

---

-   叶子相似的树-872

请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列。
举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。

如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。

如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false

---

递归实现
```C#
public bool LeafSimilar(TreeNode root1, TreeNode root2)
{
    var leaf1 = new List<int>();
    var leaf2 = new List<int>();
    __FindLeaf(leaf1, root1);
    __FindLeaf(leaf2, root2);
    return leaf1.SequenceEqual(leaf2);
}

private void __FindLeaf(List<int> leafs, TreeNode root)
{
    if (root == null)
    {
        return;
    }

__FindLeaf(leafs, root.left);
    __FindLeaf(leafs, root.right);
    if (root.left == null && root.right == null)
    {
        leafs.Add(root.val);
    }
}
```

---
栈实现的

```C#
public class Leaf : IEnumerable<int>
{
    private readonly Stack<TreeNode> _treeNode = new();

public Leaf(TreeNode root)
    {
        _treeNode.Push(root);
    }

public IEnumerator<int> GetEnumerator()
    {
        while (_treeNode.Count > 0)
        {
            var t = _treeNode.Pop();
            if (t.left == null && t.right == null)
            {
                yield return t.val;
                continue;
            }

if (t.right != null)
            {
                _treeNode.Push(t.right);
            }

if (t.left != null)
            {
                _treeNode.Push(t.left);
            }
        }
    }

IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

public bool LeafSimilarStack(TreeNode root1, TreeNode root2)
{
    var leaf1 = new Leaf(root1);
    var leaf2 = new Leaf(root1);
    using (var leafEnumerator1 = leaf1.GetEnumerator())
    {
        using (var leafEnumerator2 = leaf2.GetEnumerator())
        {
            while (leafEnumerator1.MoveNext())
            {
                if (!leafEnumerator2.MoveNext() || leafEnumerator1.Current != leafEnumerator2.Current)
                {
                    return false;
                }
            }

return !leafEnumerator2.MoveNext();
        }
    }
}
```

---

-   最大层内元素和-1161

给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层，而根节点的子节点位于第 2 层，依此类推。

请返回层内元素之和 最大 的那几层（可能只有一层）的层号，并返回其中 最小 的那个。

```C#
public int MaxLevelSum(TreeNode root)
{
    var queue = new Queue<TreeNode>();
    queue.Enqueue(root);
    var maxLayer = 0;
    var currentLayer = 0;
    var maxSum = int.MinValue;
    while (queue.Count > 0)
    {
        currentLayer++;
        var size = queue.Count;
        var sum = 0;
        for (var i = 0; i < size; i++)
        {
            var t = queue.Dequeue();
            sum += t.val;
            if (t.left != null)
            {
                queue.Enqueue(t.left);
            }

if (t.right != null)
            {
                queue.Enqueue(t.right);
            }
        }

if (sum > maxSum)
        {
            maxLayer = currentLayer;
            maxSum = sum;
        }
    }

return maxLayer;
}
```

---

-   统计二叉树中好节点的数目-1448

给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数目。

「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值。

```C#
private int _goodNum = 0;

public int GoodNodes(TreeNode root)
{
    var maxGood = root.val;
    Dfs(root, maxGood);
    return _goodNum;
}

private void Dfs(TreeNode root, int maxGood)
{
    if (root == null)
    {
        return;
    }

if (root.val >= maxGood)
    {
        maxGood = root.val;
        _goodNum++;
    }

Dfs(root.left, maxGood);
    Dfs(root.right, maxGood);
}
```

---

-    路径总和 III-437

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

```C#
private int _pathNum = 0;
private int _defaultSum = 0;

public int PathSum(TreeNode root, int targetSum)
{
    if (root == null)
    {
        return 0;
    }

var st = new List<int>();
    _defaultSum = targetSum;
    Dfs(root, ref st);
    return _pathNum;
}

private void Dfs(TreeNode root, ref List<int> visited)
{
    if (root == null)
    {
        return;
    }

visited.Add(root.val);
    var size = visited.Count;
    long sum = 0;
    for (var i = size - 1; i >= 0; i--)
    {
        var v = visited[i];
        sum += v;
        if (sum == _defaultSum)
        {
            _pathNum++;
        }
    }

Dfs(root.left, ref visited);
    Dfs(root.right, ref visited);
    visited.RemoveAt(size - 1);
}
```

---
双递归实现
```C#
public int PathSum2(TreeNode root, int targetSum)
{
    if (root == null)
    {
        return 0;
    }

_defaultSum = targetSum;
    var pathNum=RootSum(root, 0);
    pathNum+=PathSum2(root.left, targetSum);
    pathNum+=PathSum2(root.right, targetSum);
    return pathNum;
}

private int RootSum(TreeNode root, long sum)
{
    if (root == null)
    {
        return 0;
    }

sum += root.val;
    var pathNum = 0;
    if (_defaultSum == sum)
    {
        pathNum++;
    }

pathNum += RootSum(root.left, sum);
    pathNum += RootSum(root.right, sum);
    return pathNum;
}
```

---
前缀和

```C#
public int PathSum3(TreeNode root, int targetSum)
{
    if (root == null)
    {
        return 0;
    }

var prefixSum = new Dictionary<long, int>();
    prefixSum.Add(0, 1);
    _defaultSum = targetSum;
    return DoPrefixSum(root, prefixSum, 0);
}

private int DoPrefixSum(TreeNode root, Dictionary<long, int> prefixSum, long sum)
{
    if (root == null)
    {
        return 0;
    }

sum += root.val;

var ret = 0;
    ret += prefixSum.GetValueOrDefault(sum - _defaultSum, 0);

prefixSum[sum] = prefixSum.GetValueOrDefault(sum, 0) + 1;
    ret += DoPrefixSum(root.left, prefixSum, sum);
    ret += DoPrefixSum(root.right, prefixSum, sum);
    --prefixSum[sum];
    return ret;
}
```

---

-   二叉树中的最长交错路径
给你一棵以 root 为根的二叉树，二叉树中的交错路径定义如下：
选择二叉树中 任意 节点和一个方向（左或者右）。
如果前进方向为右，那么移动到当前节点的的右子节点，否则移动到它的左子节点。
改变前进方向：左变右或者右变左。
重复第二步和第三步，直到你在树中无法继续移动。
交错路径的长度定义为：访问过的节点数目 - 1（单个节点的路径长度为 0 ）。
请你返回给定树中最长 交错路径 的长度。

---

```C#
public int LongestZigZag(TreeNode root)
{
    if (root == null)
    {
        return 0;
    }

var directions = new List<int>();
    Dfs(root, 0, 0, 0);
    return _maxDirections;
}

private void Dfs(TreeNode root, int lastDir, int dir, int lastLength)
{
    if (root == null)
    {
        return;
    }

if (lastDir == dir)
    {
        lastLength = lastDir != 0 ? 1 : 0;
    }
    else
    {
        lastLength++;
    }

_maxDirections = Math.Max(lastLength, _maxDirections);

Dfs(root.left, dir, -1, lastLength);
    Dfs(root.right, dir, 1, lastLength);
}
```

---

采用深度优先遍历的方式，我们可以从顶向下访问到所有节点。并且遍历下一个子节点时，我们也能够知道子节点是属于父节点的左子树，还是右子树。

所以我们可以为每个节点缓存两个值，一个l表示到达当前节点时，该节点为左子树时的路径数，一个r表示该节点为右子树时的到达路径。 当然，一个节点要么是左子树，要么是右子树，所以l和r其中只有一个有值。

那么在遍历该节点的子节点时，如果子节点是左子树，那么它的l值就是父节点的r值加1. 如果是右子树，就是父节点的l值加1.

```C#
public int LongestZigZag2(TreeNode root)
{
    if (root == null)
    {
        return 0;
    }

Dfs2(root, 0, 0);
    return _maxDirections;
}

public void Dfs2(TreeNode root, int left, int right)
{
    _maxDirections = Math.Max(_maxDirections, Math.Max(left, right));

if (root.left != null)
    {
        Dfs2(root.left, right + 1, 0);
    }

if (root.right != null)
    {
        Dfs2(root.right, 0, left + 1);
    }
}
```

---

-   二叉树的最近公共祖先-236
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

```C#
public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
{
    var path1 = new List<TreeNode>();
    var path2 = new List<TreeNode>();
    FindPath(root, p, path1);
    FindPath(root, q, path2);
    var parent = root;
    var length = Math.Min(path1.Count, path2.Count);
    for (var i = 0; i < length; i++)
    {
        var pv1 = path1[i];
        var pv2 = path2[i];
        if (pv1.val == pv2.val)
        {
            parent = pv1;
        }
        else
        {
            break;
        }
    }

return parent;
}

private bool FindPath(TreeNode root, TreeNode t, List<TreeNode> path)
{
    if (root == null)
    {
        return false;
    }

path.Add(root);
    var size = path.Count;
    if (root.val == t.val)
    {
        return true;
    }

var result = false;
    if (root.left != null)
    {
        result = FindPath(root.left, t, path);
    }

if (!result && root.right != null)
    {
        result = FindPath(root.right, t, path);
    }

if (!result)
    {
        path.RemoveAt(size - 1);
    }

return result;
}
```

---

两个节点 p,q 分为两种情况：

p 和 q 在相同子树中
p 和 q 在不同子树中
从根节点遍历，递归向左右子树查询节点信息 递归终止条件：如果当前节点为空或等于 p 或 q，则返回当前节点

递归遍历左右子树，如果左右子树查到节点都不为空，则表明 p 和 q 分别在左右子树中，因此，当前节点即为最近公共祖先；
如果左右子树其中一个不为空，则返回非空节点

```C#
private TreeNode _parentNode = null;

public TreeNode LowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q)
{
    Dfs(root, p, q);
    return _parentNode;
}

private bool Dfs(TreeNode root, TreeNode p, TreeNode q)
{
    if (root == null)
    {
        return false;
    }

var left = Dfs(root.left, p, q);
    var right = Dfs(root.right, p, q);
    if ((left && right) || root.val == p.val || root.val == q.val)
    {
        _parentNode = root;
    }

return left || right || root.val == p.val || root.val == q.val;
}
```

---

我们可以用哈希表存储所有节点的父节点，然后我们就可以利用节点的父节点信息从 p 结点开始不断往上跳，并记录已经访问过的节点，再从 q 节点开始不断往上跳，如果碰到已经访问过的节点，那么这个节点就是我们要找的最近公共祖先。

算法

从根节点开始遍历整棵二叉树，用哈希表记录每个节点的父节点指针。
从 p 节点开始不断往它的祖先移动，并用数据结构记录已经访问过的祖先节点。
同样，我们再从 q 节点开始不断往它的祖先移动，如果有祖先已经被访问过，即意味着这是 p 和 q 的深度最深的公共祖先，即 LCA 节点。

```C#
private Dictionary<int, TreeNode> _parents = new Dictionary<int, TreeNode>();
private HashSet<int> _visited = new HashSet<int>();

public TreeNode LowestCommonAncestor3(TreeNode root, TreeNode p, TreeNode q)
{
    Dfs2(root);
    while (p != null)
    {
        _visited.Add(p.val);
        p = _parents.GetValueOrDefault(p.val, null);
    }

while (q != null)
    {
        if (_visited.Contains(q.val))
        {
            return q;
        }

q = _parents.GetValueOrDefault(q.val, null);
    }

return root;
}

private void Dfs2(TreeNode root)
{
    if (root.left != null)
    {
        _parents[root.left.val] = root;
        Dfs2(root.left);
    }

if (root.right != null)
    {
        _parents[root.right.val] = root;
        Dfs2(root.right);
    }
}
```