【数据结构练习】二叉树相关oj题集锦一

前言

1.相同的树

2.另一棵树的子树

3.翻转二叉树

4.二叉树的前序遍历

前言

编程想要学的好，刷题少不了，我们不仅要多刷题，还要刷好题！为此我开启了一个弯道超车必做好题锦集的系列，此为二叉树面试题第一篇，每篇大约5题左右。该系列会不定期更新，敬请期待！

1.相同的树

100. 相同的树https://leetcode.cn/problems/same-tree/题目描述：

代码：


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

解析：

2.另一棵树的子树

572. 另一棵树的子树https://leetcode.cn/problems/subtree-of-another-tree/ 题目描述：

代码：


class Solution {
 public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q != null || q == null && p != null) {
            return false;
        }
        if (p == null && q == null) {
            return true;
        }
        if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
      
 
   public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null) {
            return false;
        }
        //1、是不是和根节点相同
        if(isSameTree(root,subRoot)) {
            return true;
        }
        //2、判断是不是root的左子树
        if(isSubtree(root.left,subRoot)) {
            return true;
        }
        //3、右子树
        if(isSubtree(root.right,subRoot)) {
            return true;
        }
        //4、返回
        return false;
    }
}

解析：

3.翻转二叉树

226. 翻转二叉树https://leetcode.cn/problems/invert-binary-tree/ 题目描述：

代码：


   public TreeNode invertTree(TreeNode root) {
        if(root==null){
            return root;
        }
        TreeNode tmp=root.left;
        root.left=root.right;
        root.right=tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
 
    }

解析：

4.二叉树的前序遍历

144. 二叉树的前序遍历https://leetcode.cn/problems/binary-tree-preorder-traversal/

代码：


class Solution {
  public List preorderTraversal(TreeNode root) {
        List ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        ret.add(root.val);
        ret.addAll(preorderTraversal(root.left));
        ret.addAll(preorderTraversal(root.right));
        return ret;
    }
}