Simple java solution, both recurison and iteration


  • 18
    H
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // recurision method
        if (p == null && q == null) return true;
        if (p == null && q != null || p != null && q == null) return false;
        if (p.val != q.val) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
    

    public boolean isSameTree(TreeNode p, TreeNode q) {
        // iteration method
        if (p == null && q == null) return true;
        if (p == null && q != null || p != null && q == null) return false;
        Stack<TreeNode> stackP = new Stack<>();
        Stack<TreeNode> stackQ = new Stack<>();
        stackP.add(p);
        stackQ.add(q);
        while (!stackP.isEmpty() && !stackQ.isEmpty()) {
            TreeNode tmpP = stackP.pop();
            TreeNode tmpQ = stackQ.pop();
            if (tmpP.val != tmpQ.val) return false;
            if (tmpP.left != null && tmpQ.left != null) {
                stackP.push(tmpP.left);
                stackQ.push(tmpQ.left);
            } else if (tmpP.left == null && tmpQ.left == null) {
            } else {
                return false;
            }
            if (tmpP.right != null && tmpQ.right != null) {
                stackP.push(tmpP.right);
                stackQ.push(tmpQ.right);
            } else if (tmpP.right == null && tmpQ.right == null) {
            } else {
                return false;
            }
        }
        if (!stackP.isEmpty() || !stackQ.isEmpty()) return false;
        return true;
    }

  • 1
    J

    @hello_today_

    More concise style of iterative solution.

        public boolean isSameTree(TreeNode p, TreeNode q) {
            if (p == null && q == null) return true;
            if (p == null || q == null) return false;
            Stack<TreeNode> stackP = new Stack<>();
            Stack<TreeNode> stackQ = new Stack<>();
            stackP.push(p);
            stackQ.push(q);
            while (!stackP.empty() && !stackQ.empty()) {
                TreeNode np = stackP.pop();
                TreeNode nq = stackQ.pop();
                if (np.val != nq.val) return false;
                if (np.left != null && nq.left != null) {
                    stackP.push(np.left);
                    stackQ.push(nq.left);
                } else if (np.left != null || nq.left != null) {
                    return false;
                }
                if (np.right != null && nq.right != null) {
                    stackP.push(np.right);
                    stackQ.push(nq.right);
                } else if (np.right != null || nq.right != null) {
                    return false;
                }
            }
            return true;
        }
    

  • 2
    K

    @JansonLu Don't use builtin Stack in java. As per Java recommendation, Use Deque to create a stack.


  • 0
    L

    @kishorekumar What you said is very subtle.nice!!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.