leetcode 100.相同的树

原题

100.相同的树

题解

方法一 递归

方法很简单。对于两个数，判断两个根节点为空或者值相同则继续（否则返回false），之后再以同样的方式判断两个树的左分叉和右分叉是否分别“相同”。这个方法的终止条件是要么遇到值不同的节点（false），要么遇到了最末端的同时为空（true）。
本思路java代码示例：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
/*递归法
@v7fgg
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：37.2 MB, 在所有 Java 提交中击败了45.45%的用户
2020年7月30日 14:10
*/
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {       
        if(p==null&&q==null){return true;}
        if(p!=null&&q!=null&&p.val==q.val){
            return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
        }
        return false;
    }
}

当然可以把复杂的if-else结构压缩成简洁的一行代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
/*
@v7fgg
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：37.2 MB, 在所有 Java 提交中击败了50.50%的用户
2020年7月30日 14:15
*/
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        return p==null&&q==null?true:p!=null&&q!=null&&p.val==q.val?isSameTree(p.left,q.left)&&isSameTree(p.right,q.right):false;
    }
}

方法二 迭代法

准备两个栈，分别用于承装两个树的对应位置的结构。
本思路java代码示例：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
/*迭代法
@v7fgg
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：37.2 MB, 在所有 Java 提交中击败了41.82%的用户
2020年7月30日 15:54
*/
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Stack<TreeNode> pstack=new Stack<>();
        Stack<TreeNode> qstack=new Stack<>();
        pstack.push(p);
        qstack.push(q);
        while(!pstack.isEmpty()){
            TreeNode a=pstack.pop();
            TreeNode b=qstack.pop();
            if(a==null&&b==null){continue;}
            if(a==null||b==null||a.val!=b.val){return false;}
            //只有在有值且相等的时候才会执行下面，因此不会无限制添加
            pstack.push(a.left);
            pstack.push(a.right);
            qstack.push(b.left);
            qstack.push(b.right);
        }
        return true;
    }
}