二叉树刷题1

[TOC]

树的基础

102. 二叉树的层序遍历

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
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) return res;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> level = new ArrayList<>();
            int currentLevelSize = queue.size();
            for(int i=1; i<= currentLevelSize; ++i){
                TreeNode node = queue.poll();
                level.add(node.val);

                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
            }
            res.add(level);
        }
        return res;
    }
}

107. 二叉树的层序遍历 II

从根节点开始搜索，每次遍历同一层的全部节点，使用一个列表存储该层的节点值。

如果要求从上到下输出每一层的节点值，做法很直观，在遍历完一层节点之后，将存储该层节点值的列表添加到结果列表的尾部。

但这道题要求从下到上输出每一层，只要对上述操作稍作修改即可；在遍历完一层节点之后，将存储该节点值的列表添加到结果列表的头部。

为了降低在结果列表的头部添加一层节点值的列表的时间复杂度，结果列表可以使用链表的结构，在链表头部添加一层节点值的列表的时间复杂度是 O(1)O(1)。在 Java 中，由于我们需要返回的 List 是一个接口，这里可以使用链表实现；而 C++ 或 Python 中，我们需要返回一个 vector 或 list，它不方便在头部插入元素（会增加时间开销），所以我们可以先用尾部插入的方法得到从上到下的层次遍历列表，然后再进行反转。

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
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        if(root == null) return res;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> level = new ArrayList<>();
            int size = queue.size();
            for(int i=0;i<size;i++){
                TreeNode node = queue.poll();
                level.add(node.val);
                TreeNode left = node.left, right =node.right;
                if(left!=null){
                    queue.offer(left);
                }
                if(right!=null){
                    queue.offer(right);
                }
            }
            res.add(0, level);
        }
        
        return res;
    }
    
}

二叉树的遍历

前中后序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        preorder(root, res);
        return res;
    }

    public void preorder(TreeNode root, List<Integer> res){
        if(root == null) return;
        res.add(root.val);
        preorder(root.left, res);
        preorder(root.right, res);
    }
}

迭代

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root==null) return res;

        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode node = root;
        while(!stack.isEmpty() || node!=null){
            while(node!=null){
                res.add(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        return res;
    }
    
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root==null) return res;
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode node = root;
        while(!stack.isEmpty() || node!=null){
            while(node!=null){
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            res.add(node.val);
            node = node.right;
        }
        return res;
    }
  
   public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root==null) return res;

        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode prev = null;
        while(root!=null || !stack.isEmpty()){
            while(root!=null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if(root.right==null || root.right==prev){
                res.add(root.val);
                prev = root;
                root = null;
            }else{
                stack.push(root);
                root = root.right;
            }
        }

        return res;
    }
    
 }

112. 路径总和

DFS

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root==null){
            return false;
        }
        if(root.left==null && root.right==null){
            return root.val == sum;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }

}

BFS

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
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null){
            return false;
        }
        Queue<TreeNode> queNode = new LinkedList<TreeNode>();
        Queue<Integer> queVal = new LinkedList<Integer>();
        queNode.offer(root);
        queVal.offer(root.val);
        while(!queNode.isEmpty()){
            TreeNode now = queNode.poll();
            int temp = queVal.poll();
            if(now.left == null && now.right==null){
                if(temp==sum){
                    return true;
                }
                continue;
            }
            if(now.left != null){
                queNode.offer(now.left);
                queVal.offer(now.left.val + temp);
            }
            if(now.right !=null){
                queNode.offer(now.right);
                queVal.offer(now.right.val + temp);
            }
        }
        return false;
    }

}

113. 路径总和 II

问完成一件事情的所有解决方案，一般采用回溯算法（深度优先遍历）完成。做回溯算法问题一般先画图，好在这就是一个树形问题，题目已经给我们画好了示意图。

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null){
            return res;
        }

        Deque<Integer> path = new ArrayDeque<>();
        dfs(root, targetSum, path,res);
        return res;
    }

    private void dfs(TreeNode node, int sum, Deque<Integer> path, List<List<Integer>> res){
        // 递归终止条件1
        if(node == null){
            return;
        }
        // 递归终止条件2
        if(node.val == sum && node.left==null && node.right==null){
            //当前节点的值还没添加到列表中，所以要先添加，再移除
            path.addLast(node.val);
            res.add(new ArrayList<>(path));
            path.removeLast();
            return;
        }

        path.addLast(node.val);
        dfs(node.left, sum-node.val, path, res);
        // 进入左右分支的 path 是一样的，这里不用写下面两行，因为一定会调用到 path.removeLast();
        // path.removeLast();
        // path.addLast(node.val);
        dfs(node.right, sum-node.val, path, res);
        path.removeLast();
    }
  	
  	// 由于先减去了当前非空节点的值，递归终止条件写 sum==0
  	public void dfs(TreeNode node, int sum, Deque<Integer> path, List<List<Integer>> res) {
        // 递归终止条件 1：遇到空结点不再递归调用
        if (node == null) {
            return;
        }

        // 沿途结点必须选择，这个时候要做两件事：1、sum 减去这个结点的值；2、添加到 path 里
        sum -= node.val;
        path.addLast(node.val);

        // 递归终止条件 2：遇到叶子结点，sum 恰好为 0，说明从根结点到叶子结点的路径是一个符合要求的解
        if (sum == 0 && node.left == null && node.right == null) {
            // path 全局只有一份，必须做拷贝
            res.add(new ArrayList<>(path));
            // 注意：这里 return 之前必须重置
            path.removeLast();
            return;
        }

        pathSum(node.left, sum, path, res);
        pathSum(node.right, sum, path, res);
        // 递归完成以后，必须重置变量
        path.removeLast();
    }

}

437. 路径总和 III

法一 深度优先遍历

穷举所有可能，访问每一个节点node，检测以 node 为起始点且向下延伸的路径有多少种。递归遍历每个节点的所有可能的路径，然后将这些路径数目加起来即为返回结果。

  • 首先定义 $rootSum(p, val)$ 表示以节点 $p$ 为起点向下且满足路径总和为 $val$ 的路径数目。我们队二叉树上每个节点 $p$ 求出 $rootSum(p,targetSum)$，然后对这些路径数目求和为返回结果
  • 对节点 $p$ 求 $rootSum(p, targetSum)$时，以当前节点 $p$ 为目标路径的起点递归向下进行搜索。假设当前的节点$p$的值为$val$ ，对左子树和右子树进行递归搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        if(root == null){
            return 0;
        }
        int ret = rootSum(root, targetSum);
        ret += pathSum(root.left, targetSum);
        ret += pathSum(root.right, targetSum);
        return ret;
    }
    public int rootSum(TreeNode root, int targetSum){
        int ret = 0;
        if(root == null){
            return 0;
        }
        int val = root.val;
        if(val == targetSum){
            ret++;
        }
        ret += rootSum(root.left, targetSum-val);
        ret += rootSum(root.right, targetSum-val);
        return ret;
    }
}

方法二 前缀和

上一解法存在许多重复计算，定义节点的前缀和为：由根节点到当前节点的路径上所有节点的和。

利用先序遍历二叉树，记录下根节点 $root$ 到当前节点 $p$ 的路径上除当前节点以外所有节点的前缀和，在已保存的路径前缀和中查找是否存在前缀和刚好等于当前节点到根节点的前缀和 $curr - targetSum$

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
public int pathSum(TreeNode root, int targetSum) {
      Map<Integer, Integer> prefix = new HashMap<>();
      // 前缀和为0的一条路径
      prefix.put(0,1);
      // 前缀和的递归回溯
      return recursionPathSum(root, prefix, targetSum, 0);
  }

  private int recursionPathSum(TreeNode node, Map<Integer,Integer> prefix, int target, int currSum){
      if(node==null){
          return 0;
      }
      int res = 0;
      currSum += node.val;

      //---核心代码
      // 看看root到当前节点这条路上是否存在节点前缀和加target为currSum的路径
      // 当前节点->root节点反推，有且仅有一条路径，如果此前有和为currSum-target,而当前的和又为currSum,两者的差就肯定为target了
      // currSum-target相当于找路径的起点，起点的sum+target=currSum，当前点到起点的距离就是target
      res += prefix.getOrDefault(currSum - target, 0);
      // 更新路径上当前节点前缀和的个数
      prefix.put(currSum, prefix.getOrDefault(currSum, 0)+1);

      // 进入下一层
      res += recursionPathSum(node.left, prefix, target, currSum);
      res += recursionPathSum(node.right, prefix, target, currSum);

      // 回到本层，恢复状态，去除当前节点的前缀和数量
      prefix.put(currSum, prefix.get(currSum) - 1);
      return res;
  }

129. 求根节点到叶节点数字之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

    private int dfs(TreeNode root, int prevSum){
        if(root==null){
            return 0;
        }
        int sum = prevSum * 10 + root.val;
        if(root.left == null && root.right==null){
            return sum;
        }else{
            return dfs(root.left, sum) + dfs(root.right, sum);
        }
    }
}

100. 相同的树

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null){
            return true;
        }else if(p==null || q==null){
            return false;
        }else if(p.val != q.val){
            return false;
        }else{
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    }
}