The title

Given two binary trees, write a function to check if they are the same. Two trees are considered identical if they are structurally identical and the nodes have the same value.

Their thinking

The value of each node traversed is the same as the value of each node traversed. The question then becomes “how to traverse”. According to the tree knowledge, there are many ways to traverse, either by depth first or by breadth first, each of which can be achieved using recursion and iteration. Let’s look at the recursive solution

The recursive method

So let’s find a subproblem, and if the two trees are the same, which means the root nodes are the same, and the left and right subtrees are the same, then the subproblem is that every node is the same. The termination condition is the condition that the two nodes are the same. We can iterate over the subproblem using the decomposition method described above.

Recursive solution code

/ * * * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 * TreeNode left;  * TreeNode right;  * TreeNode(int x) { val = x; } *}* / class Solution {  public boolean isSameTree(TreeNode p, TreeNode q) {  // Termination conditions  if(p==null && q==null) { // It is empty at the same time  return true;  }else if(p==null || q==null) { // Not null at the same time, indicating that there are different nodes  return false;  }else if(p.val ! = q.val){ return false;  }  // Subproblem: If the left and right subtrees are the same tree, then they are the same tree  return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);  } } Copy the code

Iterative method

For iteration, we can do depth-first or breadth-first, and depth-first is a stack, last-in, first-out data structure, walking through two trees, comparing the nodes of each iteration. Or you can use breadth-first, hierarchical traversal of two trees, and you can compare each node that is traversed, and there are a lot of ways to do it, and you can try each of them, but you can just do the stack traversal. So let’s see how do we do pre-traversal using a single stack

How do I use a stack to implement a forward traversal

The preceding traversal of the tree above is: FCADBEHGM we get a stack

First put the root node F (stack structure: F)

Take the top element and print F (stack structure: empty) and put it in its right and left subtrees (EC).

Take the top of the stack and print C (E) and put his right subtree and his left subtree (ADE),

. Loop through the preceding steps until the stack is empty

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
 Stack<TreeNode> stack = new Stack<TreeNode>();  // Put the root node first  stack.push(root);  while(! stack.isEmpty()) { // Execute the loop body, first fetch the top of the stack and output, and then put the right and left nodes in order  TreeNode node = stack.pop();  res.add(Integer.valueOf(node.val));  if(node.right ! =null) {  stack.push(node.right);  }  if(node.left ! =null) {  stack.push(node.left);  }  }  return res;  } Copy the code

Iterative solution code

The above gives the use of stack to achieve the pre-order traversal code, we only need to operate on two trees at the same time, and judge each traversal to the node

public boolean isSameTreePre(TreeNode p, TreeNode q) {
        if (p == null && q == null) {            return true;
        }
        if (p == null) { return false;  }  if (q == null) { return false;  }  Stack<TreeNode> stackP = new Stack<>();  stackP.add(p);  Stack<TreeNode> stackQ = new Stack<>();  stackQ.add(q);  while(! stackP.isEmpty() || ! stackQ.isEmpty()) { TreeNode pNode = stackP.pop();  TreeNode qNode = stackQ.pop();  if (pNode == null && qNode == null) continue;  if (pNode == null) return false;  if (qNode == null) return false;  if(pNode.val ! = qNode.val) { return false;  } else {  stackP.add(pNode.right);  stackQ.add(qNode.right);  stackP.add(pNode.left);  stackQ.add(qNode.left);  }  }  return true;  } Copy the code