SameTree [source code]

public class SameTree {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        else if (p != null && q == null) return false;
        else if (p == null && q != null) return false;
        else if (p.val != q.val) return false;
        else return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

比较简单的一个题, 记得合理处理 basecase 就行了; 速度是0ms, submission 最优解;

一个稍微比较小的优化, 我刚开始只有四个 if, 但是没有用 else, 这样每一个 iteration 会 check 四个 if 全部. 但是用了 else 的话, 就可以保证每一个 iteration 只 check 一个 if 的 branch;

这个是 discussion 里面给出的 iterative 的解:

public boolean isSameTree(TreeNode p, TreeNode q) {  
         Stack<TreeNode> stack_p = new Stack <> ();         
         Stack<TreeNode> stack_q = new Stack <> ();  
         if (p != null) stack_p.push( p ) ;  
         if (q != null) stack_q.push( q ) ;  
         while (!stack_p.isEmpty() && !stack_q.isEmpty()) {  
             TreeNode pn = stack_p.pop() ;  
             TreeNode qn = stack_q.pop() ;            
             if (pn.val != qn.val) return false ;  
             if (pn.right != null) stack_p.push(pn.right) ;  
             if (qn.right != null) stack_q.push(qn.right) ;  
             if (stack_p.size() != stack_q.size()) return false ;  
             if (pn.left != null) stack_p.push(pn.left) ;                          
             if (qn.left != null) stack_q.push(qn.left) ;  
             if (stack_p.size() != stack_q.size()) return false ;  
         }             
         return stack_p.size() == stack_q.size() ;     
 }

看了一下, 基本上没有什么特别的地方, 就是用两个 stack 的 size 的对比来判断Null, 这个稍微有点新意.

Problem Description

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.

Difficulty:Easy
Category:Algorithms
Acceptance:46.20%
Contributor: LeetCode
Companies
bloomberg
Related Topics
tree depth-first search

/**

• Definition for a binary tree node.
• public class TreeNode {
• int val;
• TreeNode left;
• TreeNode right;
• TreeNode(int x) { val = x; }
• }
  */