Leetcode brush question: binary tree 13 (the same tree)

100. Same tree

Force button topic link

Given two binary trees , Write a function to verify that they are the same .

If two trees are the same in structure , And the nodes have the same value , They are the same .

Fool's method , Press p Track traversal run again , Press again q Track traversal run again .

package com.programmercarl.tree;

import lombok.val;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/** * @ClassName IsSameTree * @Descriotion TODO * @Author nitaotao * @Date 2022/7/4 19:50 * @Version 1.0 **/
public class IsSameTree {
    
    public boolean isSameTree(TreeNode p, TreeNode q) {
    
        if (p == null && q == null) {
    
            return true;
        }
        TreeNode tempP=p;
        TreeNode tempQ=q;
        Stack<TreeNode> stackP = new Stack<TreeNode>();
        Stack<TreeNode> stackQ = new Stack<TreeNode>();
        while (p != null || !stackP.isEmpty()) {
    
            if (p != null) {
    
                stackP.push(p);
                stackQ.push(q);
                p = p.left;
                if (q == null || stackP.isEmpty()) {
    
                    return false;
                }
                q = q.left;
            } else {
    
                p = stackP.pop();
                q = stackQ.pop();
                if (p.val != q.val) {
    
                    return false;
                }
                p = p.right;
                q = q.right;
            }
        }

        Stack<TreeNode> stackp = new Stack<TreeNode>();
        Stack<TreeNode> stackq = new Stack<TreeNode>();
        while (tempQ != null || !stackq.isEmpty()) {
    
            if (tempQ != null) {
    
                stackp.push(tempP);
                stackq.push(tempQ);
                tempQ= tempQ.left;
                if (tempP == null || stackp.isEmpty()) {
    
                    return false;
                }
                tempP= tempP.left;
            } else {
    
                tempP = stackp.pop();
                tempQ = stackq.pop();
                if (tempP.val != tempQ.val) {
    
                    return false;
                }
                tempP = tempP.right;
                tempQ = tempQ.right;
            }
        }

        return true;
    }
}

Look at the boss recursive + iteration

    public boolean isSameTree(TreeNode p, TreeNode q) {
    
        return compare(p, q);
    }

    // It can be seen as two subtrees , Left and right subtrees 
    private boolean compare(TreeNode left, TreeNode right) {
    
        if (left == null && right == null) {
    
            return true;
        }
        // Not both are empty 
        // Where is empty 
        if (left == null || right == null) {
    
            return false;
        }
        if (left.val != right.val) {
    
            return false;
        }
        boolean leftResult = compare(left.left, right.left);
        boolean rightResult = compare(left.right, right.right);
        return leftResult && rightResult;
    }