leetcode刷题-树

Posted on

简单题

100. 相同的树

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

解题思路：
先判空树，然后比较两树的结点值是否相同，再判断p左树空，q左树不空，q右树空，p右树不空的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    boolean flag = true;
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null && q==null)
            return true;
        if((p != null && q == null) || (p == null && q != null))
            return false;
 
        isSame(p,q);
        return flag;
    }
    
    public void isSame(TreeNode p, TreeNode q){
        if(p.val != q.val){
            flag = false;
        }
 
        if ((p.left == null && q.left != null) || (p.left != null && q.left == null))
            flag = false;
 
        if (p.left != null && q.left != null){
            isSame(p.left,q.left);
        }
 
        if ((p.right == null && q.right != null) || (p.right != null && q.right == null))
            flag = false;
 
        if (p.right != null && q.right != null){
            isSame(p.right,q.right);
        }
 
    }
}

101. 对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

1
2
3
4
5
    1
   / \
  2   2
 / \ / \
3  4 4  3

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
     public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }

        return checkNodes(root.left, root.right);
    }

    public boolean checkNodes(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null) {
            return true;
        }
        if (node1 == null || node2 == null) {
            return false;
        }
        if (node1.val != node2.val) {
            return false;
        } else {
            return checkNodes(node1.left, node2.right) && checkNodes(node1.right, node2.left);
        }
    }


}

104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7],深度是3

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
  
  public int maxDepth(TreeNode root) {
    if (root == null) {
      return 0;
    } else {
      int left_height = maxDepth(root.left);
      int right_height = maxDepth(root.right);
      return java.lang.Math.max(left_height, right_height) + 1;
    }
  }

}

迭代

解题思路：
所以我们从包含根结点且相应深度为 1 的栈开始。然后我们继续迭代：将当前结点弹出栈并推入子结点。每一步都会更新深度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import javafx.util.Pair;
import java.lang.Math;

class Solution {
  public int maxDepth(TreeNode root) {
    Queue<Pair<TreeNode, Integer>> stack = new LinkedList<>();
    if (root != null) {
      stack.add(new Pair(root, 1));
    }

    int depth = 0;
    while (!stack.isEmpty()) {
      Pair<TreeNode, Integer> current = stack.poll();
      root = current.getKey();
      int current_depth = current.getValue();
      if (root != null) {
        depth = Math.max(depth, current_depth);
        stack.add(new Pair(root.left, current_depth + 1));
        stack.add(new Pair(root.right, current_depth + 1));
      }
    }
    return depth;
  }
};

107. 二叉树的层次遍历 II

给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：
给定二叉树 [3,9,20,null,null,15,7],

1
2
3
4
5
 3
 / \
9  20
  /  \
 15   7

1
2
3
4
5
[
  [15,7],
  [9,20],
  [3]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public List<List<Integer>> levelOrderBottom(TreeNode root) {
      LinkedList<List<Integer>> result = new LinkedList<List<Integer>>();

      if (root == null) {
          return result;
      }
      Queue<TreeNode> queue = new LinkedList<TreeNode>();
      queue.add(root);
      int i = queue.size(); // 记录每层的结点个数
      TreeNode tempNode = null;
      List<Integer> singleLevel = new ArrayList<>();
      while (!queue.isEmpty()) {
          if (i == 0) {// 一层记录结束
              //
              result.addFirst(singleLevel);

              i = queue.size();
              singleLevel = new ArrayList<>();
          }
          tempNode = queue.poll();
          singleLevel.add(tempNode.val);

          --i;

          if (tempNode.left != null) {
              queue.add(tempNode.left);
          }
          if (tempNode.right != null) {
              queue.add(tempNode.right);
          }

      }
      result.addFirst(singleLevel);
      return result;
  }

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public List<List<Integer>> levelOrderBottom(TreeNode root) {
    LinkedList<List<Integer>> result = new LinkedList<List<Integer>>();

    levelRecursion(root, result, 0);

    return result;
}

/**
 * 递归方法
 */
private void levelRecursion(TreeNode node,
        LinkedList<List<Integer>> result, int level) {
    if (node == null) {
        return;
    }
    if (result.size() < level + 1) {// 说明还需要添加一行
        result.addFirst(new ArrayList<Integer>());
    }
    result.get(result.size() - 1 - level).add(node.val);

    levelRecursion(node.left, result, level + 1);
    levelRecursion(node.right, result, level + 1);
}

基础回顾

树的遍历(DFS思想)

1
2
3
4
5
6
7
     A
    / \
   B   C
 /  \  / \
D   E  F  G   
\
H

  1. 中序遍历:左子树——》根节点——》右子树

    1
    2
    3
    4
    5
    6
    7
    public void infixOrder(Node current){
        if(current != null){
            infixOrder(current.leftChild);
            System.out.print(current.data+" ");
            infixOrder(current.rightChild);
        }
    }

  2. 前序遍历:根节点——》左子树——》右子树

    1
    2
    3
    4
    5
    6
    7
    public void preOrder(Node current){
        if(current != null){
            System.out.print(current.data+" ");
            preOrder(current.leftChild);
            preOrder(current.rightChild);
        }
    }

  3. 后序遍历:左子树——》右子树——》根节点

    1
    2
    3
    4
    5
    6
    7
    public void postOrder(Node current){
        if(current != null){
            postOrder(current.leftChild);
            postOrder(current.rightChild);
            System.out.print(current.data+" ");
        }
    }