Синхронный обход деревьев

До этого мы работали с одним деревом. Но бывают задачи, где нужно обходить два дерева одновременно — сравнивая узлы в одних и тех же позициях. Функция принимает два указателя вместо одного и синхронно спускается по обоим деревьям.

Разбор задачи

Даны корни двух бинарных деревьев. Нужно определить, идентичны ли они — совпадают ли структура и значения во всех узлах.

Базовый случай теперь сложнее — нужно обработать три ситуации: оба узла пустые, только один пустой, оба непустые. Можно записать это развёрнуто:

/**
 * @param {TreeNode} node1
 * @param {TreeNode} node2
 * @returns {boolean}
 */
export function isSameTree(node1, node2) {
  // оба пустые — деревья совпадают
  if (node1 === null && node2 === null) {
    return true;
  }
  // только один пустой — структура разная
  if (node1 === null || node2 === null) {
    return false;
  }
  // значения не совпадают
  if (node1.val !== node2.val) {
    return false;
  }

  return isSameTree(node1.left, node2.left) && isSameTree(node1.right, node2.right);
}

/**
 * @param {TreeNode} node1
 * @param {TreeNode} node2
 * @returns {boolean}
 */
export function isSameTree(node1, node2) {
  // оба пустые — деревья совпадают
  if (node1 === null && node2 === null) {
    return true;
  }
  // только один пустой — структура разная
  if (node1 === null || node2 === null) {
    return false;
  }
  // значения не совпадают
  if (node1.val !== node2.val) {
    return false;
  }

  return isSameTree(node1.left, node2.left) && isSameTree(node1.right, node2.right);
}

/**
 * @param {TreeNode} node1
 * @param {TreeNode} node2
 * @returns {boolean}
 */
export function isSameTree(node1, node2) {
  // оба пустые — деревья совпадают
  if (node1 === null && node2 === null) {
    return true;
  }
  // только один пустой — структура разная
  if (node1 === null || node2 === null) {
    return false;
  }
  // значения не совпадают
  if (node1.val !== node2.val) {
    return false;
  }

  return isSameTree(node1.left, node2.left) && isSameTree(node1.right, node2.right);
}

/**
 * @param {TreeNode} node1
 * @param {TreeNode} node2
 * @returns {boolean}
 */
export function isSameTree(node1, node2) {
  // оба пустые — деревья совпадают
  if (node1 === null && node2 === null) {
    return true;
  }
  // только один пустой — структура разная
  if (node1 === null || node2 === null) {
    return false;
  }
  // значения не совпадают
  if (node1.val !== node2.val) {
    return false;
  }

  return isSameTree(node1.left, node2.left) && isSameTree(node1.right, node2.right);
}

/**
 * @param {TreeNode} node1
 * @param {TreeNode} node2
 * @returns {boolean}
 */
export function isSameTree(node1, node2) {
  // оба пустые — деревья совпадают
  if (node1 === null && node2 === null) {
    return true;
  }
  // только один пустой — структура разная
  if (node1 === null || node2 === null) {
    return false;
  }
  // значения не совпадают
  if (node1.val !== node2.val) {
    return false;
  }

  return isSameTree(node1.left, node2.left) && isSameTree(node1.right, node2.right);
}

/**
 * @param {TreeNode} node1
 * @param {TreeNode} node2
 * @returns {boolean}
 */
export function isSameTree(node1, node2) {
  // оба пустые — деревья совпадают
  if (node1 === null && node2 === null) {
    return true;
  }
  // только один пустой — структура разная
  if (node1 === null || node2 === null) {
    return false;
  }
  // значения не совпадают
  if (node1.val !== node2.val) {
    return false;
  }

  return isSameTree(node1.left, node2.left) && isSameTree(node1.right, node2.right);
}

А можно компактнее:

public class Solution
{
    public static bool IsSameTree(TreeNode node1, TreeNode node2)
    {
        if (node1 == null || node2 == null)
        {
            return node1 == node2;
        }

        return node1.val == node2.val
               && IsSameTree(node1.left, node2.left)
               && IsSameTree(node1.right, node2.right);
    }
}

bool isSameTree(TreeNode* node1, TreeNode* node2) {
    if (node1 == nullptr || node2 == nullptr) {
        return node1 == node2;
    }

    return node1->val == node2->val
        && isSameTree(node1->left, node2->left)
        && isSameTree(node1->right, node2->right);
}

package main

func isSameTree(node1 *TreeNode, node2 *TreeNode) bool {
    if node1 == nil || node2 == nil {
        return node1 == node2
    }

    return node1.val == node2.val &&
        isSameTree(node1.left, node2.left) &&
        isSameTree(node1.right, node2.right)
}

public class Solution {

    public boolean isSameTree(TreeNode node1, TreeNode node2) {
        if (node1 == null || node2 == null) {
            return node1 == node2;
        }

        return node1.val == node2.val
                && isSameTree(node1.left, node2.left)
                && isSameTree(node1.right, node2.right);
    }
}

def is_same_tree(node1: TreeNode, node2: TreeNode) -> bool:
    if node1 is None or node2 is None:
        return node1 is node2

    return node1.val == node2.val \
        and is_same_tree(node1.left, node2.left) \
        and is_same_tree(node1.right, node2.right)

/**
 * @param {TreeNode} node1
 * @param {TreeNode} node2
 * @returns {boolean}
 */
export function isSameTree(node1, node2) {
  if (node1 === null || node2 === null) {
    return node1 === node2;
  }

  return node1.val === node2.val
    && isSameTree(node1.left, node2.left)
    && isSameTree(node1.right, node2.right);
}

Трюк в том, что условие (if node1 is None or node2 is None) ловит сразу оба случая: если оба пустые — вернём True (они равны), если только один — вернём False.

Оценка сложности

Время: O(n), где n — минимальное число узлов в одном из деревьев
Память: O(h), где h — минимальная высота одного из деревьев

Маркеры синхронного обхода: в задаче фигурируют два дерева (или два поддерева одного дерева) и нужно сравнивать узлы в одних и тех же или симметричных позициях.