Day 20 二叉树补补补

226.翻转二叉树

迭代方式统一写法的中序是可以的

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop();
                if (node->right) st.push(node->right);  // 右
                st.push(node);                          // 中
                st.push(NULL);
                if (node->left) st.push(node->left);    // 左
 
            } else {
                st.pop();
                node = st.top();
                st.pop();
                swap(node->left, node->right);          // 节点处理逻辑
            }
        }
        return root;
    }
};

这个代码是一个非递归版本的二叉树翻转实现，它使用了一个栈（stack）来模拟递归过程。这种方法也被称为深度优先搜索（DFS）的迭代版本。

首先，如果根节点不为空，将其推入栈中。然后进入一个循环，只要栈不为空就继续执行循环。在每次循环中，首先取出栈顶的节点。如果这个节点不为空，那么将其右子节点、自己、一个空节点（作为标记），左子节点依次入栈。然后进入下一次循环。

如果栈顶的节点为空，那么将其弹出，然后再次取出栈顶的节点，并将其弹出，然后交换这个节点的左右子节点。这样，就完成了对这个节点的处理。

这个过程会一直进行，直到栈变为空，此时所有的节点都已经被处理过，二叉树也就完成了翻转。

举个例子，如果输入的二叉树是：

  4
 / \
2   7

初始： [4]

推入4的左右子节点和4自身： [7, 4, NULL, 2]

弹出2和NULL，交换2的左右子节点： [7, 4]

推入4的左右子节点和4自身： [4, NULL, 7]

弹出7和NULL，交换7的左右子节点： [4]

推入4的左右子节点和4自身： [NULL, 4]

弹出4和NULL，交换4的左右子节点： []

举个例子说明：节点处理逻辑

假设我们有以下的二叉树：

    4
   / \
  2   7
 / \ / \
1  3 6  9

我们首先将根节点4推入栈中，然后进入while循环。

在循环中，我们首先检查栈顶元素。因为栈顶元素是4，不是NULL，所以我们进入if分支。在这个分支中，我们首先将4弹出，然后将其右子节点7、自身4、NULL标记、左子节点2依次推入栈中。此时栈的内容为：[2, NULL, 4, 7]。

然后我们再次进入while循环，取出栈顶元素2，因为2不是NULL，所以我们同样进入if分支。我们将2弹出，然后将其右子节点3、自身2、NULL标记、左子节点1依次推入栈中。此时栈的内容为：[1, NULL, 2, 3, NULL, 4, 7]。

接下来我们取出栈顶元素1，因为1是叶节点，没有子节点，所以我们只需要将1和NULL标记推入栈中。此时栈的内容为：[NULL, 1, NULL, 2, 3, NULL, 4, 7]。

接下来我们取出栈顶元素NULL，因为这是一个NULL标记，所以我们进入else分支。在这个分支中，我们首先将NULL弹出，然后取出栈顶元素1，并将其弹出，然后交换1的左右子节点。因为1是叶节点，没有子节点，所以这个交换操作没有实际效果。此时栈的内容为：[NULL, 2, 3, NULL, 4, 7]。

我们再次进入while循环，取出栈顶元素NULL，然后进入else分支，弹出NULL，取出栈顶元素2，并将其弹出，然后交换2的左右子节点。此时2的左右子节点被交换，变为：

  2
 / \
3   1

此时栈的内容为：[3, NULL, 4, 7]。

这个过程会一直进行，直到栈变为空，此时所有的节点都已经被处理过，二叉树也就完成了翻转。最后翻转后的二叉树为：

    4
   / \
  7   2
 / \ / \
9  6 3  1

在这个代码中，NULL在栈中的作用主要是作为一个标记，用来表示当前节点的左右子节点都已经被访问过了，下一步需要处理当前节点（交换其左右子节点）。

当我们从栈顶取出一个节点时，如果这个节点不是NULL，那么我们会将其右子节点、自己、NULL标记、左子节点依次入栈。这样，我们就可以在下一次循环中继续访问其左子节点。同时，NULL标记和自己被放在了左子节点之后，这保证了我们在处理完左子节点之后，会回到自己，进行处理。

当我们从栈顶取出一个节点时，如果这个节点是NULL，那么我们知道下一个节点就是需要处理的节点，因为其左右子节点都已经被处理过了。我们会将NULL弹出，然后取出下一个节点，交换其左右子节点。

所以，你可以把NULL看作是一个标记，它的出现表示当前节点的左右子节点都已经被访问过了，下一步需要处理当前节点。

101. 对称二叉树

另一棵树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

=深度优先搜索暴力匹配=
class Solution {
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if (!root) {
            return false;
        }
        if (isSameTree(root, subRoot)) {
            return true;
        }
        return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
    }
 
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (!p && !q) {
            return true;
        }
        if (!p || !q) {
            return false;
        }
        return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};
 
实际上是在主树root的每个节点上，都尝试与子树subRoot进行完全匹配。
我们在函数isSubtree中，对root进行深度优先搜索。对于root中的每个节点，我们都调用isSameTree函数来检查从该节点开始的子树是否与subRoot相同。
isSameTree函数也是一个深度优先搜索，它会递归地比较两棵树的左子树和右子树是否相同。
因此，这个算法的时间复杂度是O(mn)，其中m是主树root的节点数，n是子树subRoot的节点数。这是因为对于root中的每个节点，我们都可能需要查看subRoot中的所有节点来进行匹配。
空间复杂度是O(m)，这是因为在最坏的情况下，我们可能需要递归地访问root中的所有节点。这将在调用栈中产生m个函数调用，因此需要O(m)的空间。

104.二叉树的最大深度

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

层序遍历的思想

• 创建一个队列que，用于存储待处理的节点。
• 使用一个while循环，当队列不为空时，执行以下操作：
• 记录当前层的节点数量size（队列的大小）。
• 将depth加1，因为我们正在进入新的一层。
• 遍历当前层的所有节点（通过for循环，从0到size-1）
• 当队列为空时，说明已经遍历完了所有节点，此时depth的值即为二叉树的最大深度。
• 返回depth作为结果。

• class Solution {
  public:
      int maxDepth(TreeNode* root) {
          if(root==NULL) return 0;
          int depth=0;
          queue<TreeNode*> que;
          que.push(root);
          while(!que.empty()){
              int size=que.size();
              depth++;
              for(int i=0;i<size;i++){
                  TreeNode* node=que.front();
                  que.pop();
                  if(node->left) que.push(node->left);
                  if(node->right) que.push(node->right);
              }
          }
          return depth;
      }
  };
  

  递归法求解二叉树的最大深度：

• 确定递归函数的参数和返回值参数：

• 1. 树的根节点TreeNode* node。

• 2. 返回值：这棵树的深度，类型为int

• 确定终止条件：

• “如果当前节点为空（node == NULL），则返回0”

• 确定单层递归的逻辑：
• 先求它的左子树的深度，再求右子树的深度，最后取左右深度最大的数值 再+1 （加1是因为算上当前中间节点）就是目前节点为根节点的树的深度。

• class Solution {
  public:
      int getdepth(TreeNode* node) {
          if (node == NULL) return 0;
          int leftdepth = getdepth(node->left);       // 左
          int rightdepth = getdepth(node->right);     // 右
          int depth = 1 + max(leftdepth, rightdepth); // 中
          return depth;
      }
      int maxDepth(TreeNode* root) {
          return getdepth(root);
      }
  };
  

可以深度优先搜索(DFS)和回溯的思想。前序的话求深度：

1. 递归函数是： void getDepth(TreeNode* node, int depth)
   递归函数需要两个参数，当前的节点(node)和当前的深度(depth)。

2. 返回值是：
   在每次递归调用中 getDepth 函数都没有明确的返回值，它将最终结果保存在了成员变量 result 中。在最后的主函数 maxDepth 中返回的是 result， 这个 result 表示二叉树的最大深度。

3. 终止条件是：if (node->left == NULL && node->right == NULL) return ;
   这个条件用于判断当前节点为叶子节点，也就是该节点既没有左孩子也没有右孩子，该路径结束，返回上一级节点。

4. 单层的递归逻辑是：

   • 首先，比较当前深度和最大深度，如果当前深度大于最大深度，则更新最大深度。
   • 如果当前节点是叶子节点，结束当前递归。
   • 如果当前节点有左孩子，深度+1，递归遍历左子树，并在遍历完之后，深度-1，实现回溯。
   • 如果当前节点有右孩子，深度+1，递归遍历右子树，并在遍历完之后，深度-1，实现回溯。

111.二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

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

迭代法：

前序遍历（根节点->左子树->右子树）：

1. 访问当前节点，判断是否为空，判断终止条件

2. 更新最小深度: 如果当前访问的节点是叶子节点，则更新最小深度。result = min(result, depth);。

3.递归遍历左右子树: 如果当前节点不为空且不是叶子节点，会依次递归遍历左子树和右子树。

getdepth(node->left, depth + 1);和getdepth(node->right, depth + 1);.

4.当左右子节点都递归完毕访问的节点是叶子节点更新最小深度。

后序遍历（左子树->右子树->根节点）：

1. 如果节点为空，则返回深度0，递归结束。这是递归的边界条件。

2. 它首先递归访问左右子树，然后在所有子节点被处理完之后，再更新当前节点的深度。int leftDepth = getDepth(node->left);和int rightDepth = getDepth(node->right);。

更新当前节点的深度：只有在访问完子节点之后，才会根据左右子树的深度来更新当前节点的深度。

如果左子树为空且右子树不为空，意味着当前节点不可能是最小深度的节点，因为右子树还没有被完全遍历。将当前节点的深度更新为右子树的深度加1。if (node->left == NULL && node->right != NULL) { return 1 + rightDepth;}。

如果右子树为空且左子树不为空，意味着当前节点也不可能是最小深度的节点，因为左子树还未完全遍历。这种情况下，将当前节点的深度更新为左子树的深度加1。if (node->left != NULL && node->right == NULL) {return 1 + leftDepth; }。

当左右子树都不为空时，当前节点的深度为左右子树深度的较小值再加1。

层序遍历：只有当左右孩子都为空的时候，说明遍历到最低点了。返回depth

222.完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树方法：

• 当完全二叉树的左子树和右子树的高度相等时，说明左子树是一棵满二叉树，可以直接通过公式 (2 << leftDepth) - 1 计算出节点数。 (2<<leftDepth) 的作用相当于 2^(leftDepth+1)，是左子树的节点数加根节点。

• 反之，如果左子树和右子树的高度不等，那么右子树的高度比左子树小一且右子树也是满二叉树，左子树仍然是一棵完全二叉树。这种情况下，递归分别求解左子树和右子树的节点数量，两者之和再加上根节点就是当前完全二叉树的节点数量。

if (root == nullptr) return 0;

1. 接下来定义了两个指针left和right，同时定义了两个变量leftDepth和rightDepth来记录左右子树的深度。

TreeNode* left = root->left;
TreeNode* right = root->right;
int leftDepth = 0, rightDepth = 0;

1. 这两个while循环用来获取左子树和右子树的深度。根据完全二叉树的性质，对于左子树，我们持续向左节点深入；对于右子树，我们持续向右节点深入。

while (left) {
    left = left->left;
    leftDepth++;
}
while (right) {
    right = right->right;
    rightDepth++;
}

1. 接下来判断左右子树的深度。如果它们的深度相同，那么这棵树就是一颗完全二叉树，根据完全二叉树的节点总数公式，我们可以缩写为 return (2 << leftDepth) - 1 来求出节点总数，这里 (2 << leftDepth) 相当于 pow(2, leftDepth+1)，我们的目的是求 2^(深度+1)-1。

if (leftDepth == rightDepth) {
    return (2 << leftDepth) - 1;
}

1. 若不是完全二叉树，则递归计算左右子树的节点数量并返回总和加一(加一是因为还要算上根节点)。

return countNodes(root->left) + countNod

所以，无论怎样，这种方法都会覆盖到完全二叉树的所有节点，所以不会漏掉任何节点

110.平衡二叉树

给定一个二叉树，判断它是否是 平衡二叉树

平衡二叉树的定义是：它是一棵空树或它的左右子树的高度差的绝对值不超过 1，并且左右两个子树都是一颗平衡二叉树。换句话说，平衡二叉树要求每个节点的左右子树的高度差不超过1。求高度并判断。

而高度只能从下到上去查，所以只能后序遍历（左右中）

平衡二叉树的定义是：它是一棵空树或它的左右子树的高度差的绝对值不超过 1，并且左右两个子树都是一颗平衡二叉树。换句话说，平衡二叉树要求每个节点的左右子树的高度差不超过1。

为了判断一个二叉树是否是平衡的，你需要从底部开始，先判断子树是不是平衡的，再判断父节点是否平衡。每一个节点都这样判断。这就需要后序遍历（左-右-中）。因为在前序和中序遍历（先访问父节点）时，我们无法获取子树的相关信息。

所以，我们首先遍历到底部（左右子节点），计算出它们的高度，然后返回给父节点，让父节点去判断“我是不是平衡的”。如果非平衡，我们就直接返回非平衡的结果。而这恰恰是维护、“更新”高度所必需的，也是后序遍历可以给我们带来的便利之处。让我们在获取所有必要信息后再做决定。

这也就是为什么我们在计算最大深度问题中也用到后序遍历的原因，首先遍历子节点获取深度，然后根据子节点的深度计算出当前节点的深度。

所以，后序遍历特别适合这类需要从下至上（从子节点到父节点）进行操作的场合。

要求比较高度。

1. 明确递归函数的参数和返回值

参数：当前传入节点。 返回值：以当前传入节点为根节点的树的高度。

如果当前传入节点为根节点的二叉树已经不是二叉平衡树了，还返回高度的话就没有意义了。、那标记为-1。

2.明确终止条件

在递归的过程中，当递归到达叶子节点时，会试图继续访问它的子节点，也就是空节点。这时，我们返回0，表示已经到达树的最底部。

3. 明确单层递归的逻辑

分别求出其左右子树的高度，然后如果差值小于等于1，则返回当前二叉树的高度，否则返回-1，表示已经不是二叉平衡树了。

class Solution {
public:
    // 返回以该节点为根节点的二叉树的高度，如果不是平衡二叉树了则返回-1
    int getHeight(TreeNode* node) {
        if (node == NULL) {
            return 0;
        }
        int leftHeight = getHeight(node->left);
        if (leftHeight == -1) return -1;
        int rightHeight = getHeight(node->right);
        if (rightHeight == -1) return -1;
        return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);
    }
    bool isBalanced(TreeNode* root) {
        return getHeight(root) == -1 ? false : true;
    }
};

257. 二叉树的所有路径

1. 递归函数需要三个参数，当前的节点 (cur), 目前的路径 (path) 和结果 (result)。traversal 函数都没有明确的返回值，它将所有的结果保存在了参数 result

2. 终止条件是：
if (cur->left == NULL && cur->right == NULL)，这个条件用于判断当节点是叶子节点时，也就是该节点既没有左孩子也没有右孩子时，我们就在结果result中添加当前的路径。

3. 单层的递归逻辑是：

• 首先，将当前节点的值加入到路径中。
• 如果当前节点是叶子节点，将路径转换为字符串，并加入到结果result中，结束当前递归。
• 如果当前节点有左孩子，递归遍历左子树，并在遍历完之后，将路径中最后一个节点弹出，实现回溯。
• 如果当前节点有右孩子，递归遍历右子树，并在遍历完之后，将路径中最后一个节点弹出，实现回溯。

if (cur->left) traversal(cur->left, path + "->", result); // 左  回溯就隐藏在这里

当我们调用traversal(cur->left, path + "->", result)时，实际上创建了一个新的字符串path + "->"，并且在这个新的字符串的基础上继续递归。这个新的字符串并不会影响到原来的path字符串。因此，当递归返回到上一级的时候，path还是其原来的值，这就完成了回溯。