Same Tree

描述

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

分析

无

递归版

  1. // Same Tree
  2. // 递归版，时间复杂度O(n)，空间复杂度O(logn)
  3. public class Solution {
  4.     public boolean isSameTree(TreeNode p, TreeNode q) {
  5.         if (p == null && q == null) return true;   // 终止条件
  6.         if (p == null || q == null) return false;  // 剪枝
  7.         return p.val == q.val      // 三方合并
  8.                 && isSameTree(p.left, q.left)
  9.                 && isSameTree(p.right, q.right);
  10.     }
  11. }

迭代版

  1. // Same Tree
  2. // 迭代版，时间复杂度O(n)，空间复杂度O(logn)
  3. public class Solution {
  4.     public boolean isSameTree(TreeNode p, TreeNode q) {
  5.         Stack<TreeNode> s = new Stack<>();
  6.         s.push(p);
  7.         s.push(q);
  9.         while(!s.empty()) {
  10.             p = s.pop();
  11.             q = s.pop();
  13.             if (p == null && q == null) continue;
  14.             if (p == null || q == null) return false;
  15.             if (p.val != q.val) return false;
  17.             s.push(p.left);
  18.             s.push(q.left);
  20.             s.push(p.right);
  21.             s.push(q.right);
  22.         }
  23.         return true;
  24.     }
  25. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/binary-tree/traversal/same-tree.html