【2错1对-1】Same Tree

https://leetcode.com/problems/same-tree/

日期	是否一次通过	comment
2018-12-12 20:37	非递归没思路，递归有部分思路	思维不够灵活
2019-01-13 16:06	忽视了何时返回true和false	思维不够灵活

image.png

（来源：https://leetcode.com/problems/same-tree/）

递归

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

非递归

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        
        Queue<TreeNode[]> nodesQ = new LinkedList<>();
        nodesQ.offer(new TreeNode[]{p, q});
        while(!nodesQ.isEmpty()) {
            TreeNode[] nodes = nodesQ.poll();
            if(nodes[0] == null || nodes[1] == null) {
                if(!(nodes[0] == null && nodes[1] == null)) {
                    return false;
                }
                continue;
            } 
            if(nodes[0].val != nodes[1].val) {
                return false;
            }
            
            nodesQ.offer(new TreeNode[]{nodes[0].left, nodes[1].left});
            nodesQ.offer(new TreeNode[]{nodes[0].right, nodes[1].right});
            
        }
        return true;
    }
}

or

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        
        if(p == null || q == null) {
            return p == q;
        }
        
        Stack<TreeNode> pStack = new Stack<>();
        Stack<TreeNode> qStack = new Stack<>();
        
        pStack.push(p);
        qStack.push(q);
        
        while(!pStack.isEmpty() && !qStack.isEmpty()) {
            TreeNode nodeP = pStack.pop();
            TreeNode nodeQ = qStack.pop();
            if(nodeP.val != nodeQ.val) {
                return false;
            }
            
            if(nodeP.left != null) {
                pStack.push(nodeP.left);
            }
            if(nodeQ.left != null) {
                qStack.push(nodeQ.left);
            }
            if(pStack.size() != qStack.size()) {
                return false;
            }
            if(nodeP.right != null) {
                pStack.push(nodeP.right);
            }
            if(nodeQ.right != null) {
                qStack.push(nodeQ.right);
            }
            if(pStack.size() != qStack.size()) {
                return false;
            }
            
        }
        
        return pStack.isEmpty() && qStack.isEmpty();
    }
}