LeetCode Identical Binary Tree 相同二叉树

Love The Way You Lie 2022-06-08 03:17 161阅读 0赞

题目描述：

Check if two binary trees are identical. Identical means the two binary trees have the same structure and every identical position has the same value.

样例输入：

1             1
       / \           / \   2   2   and   2   2
     /             /
    4             4

1             1
       / \           / \   2   3   and   2   3
     /               \ 4                 4

样例输出：

true
    false

解法一：

有树的地方就有递归

private boolean isIdenticalRecursion(TreeNode a, TreeNode b) {
       if (a == null && b == null) {
            return true;
        }
        if ((a == null && b != null) || (a != null && b == null) || (a.val != b.val)) {
            return false;
        }
        return isIdenticalRecursion(a.left, b.left) && isIdenticalRecursion(a.right, b.right);
    }

解法二：

递归能实现的循环也能实现

private boolean isIdenticalPreOrder(TreeNode a, TreeNode b) {
         Stack<TreeNode> stack1 = new Stack<>();
         Stack<TreeNode> stack2 = new Stack<>();
         stack1.push(a);
         stack2.push(b);
         while (!stack1.empty() && !stack2.empty()) {
             TreeNode tmp1 = stack1.pop();
             TreeNode tmp2 = stack2.pop();
             if (tmp1.val!=tmp2.val){
                 return false;
             }
             if (tmp1.right!=null){
                 stack1.push(tmp1.right);
             }
             if (tmp2.right!=null){
                 stack2.push(tmp2.right);
             }
             if (stack1.size()!=stack2.size()){
                 return false;
             }
             if (tmp1.left!=null){
                 stack1.push(tmp1.left);
             }
             if (tmp2.left!=null){
                 stack2.push(tmp2.left);
             }
             if (stack1.size()!=stack2.size()){
                 return false;
             }
         }
         return stack1.size() == stack2.size();
     }