二叉树汇总

遍历问题

226. 翻转二叉树

力扣传送门

思路：递归，DFS遍历
利用DFS遍历每个节点时，交换左右子树的节点引用(经典两数交换)

 public TreeNode invertTree(TreeNode root) {
      if(root == null) return null;
      TreeNode tmp = root.left;
      root.left = invertTree(root.right);
      root.right = invertTree(tmp);
      return root;
  }
1
2
3
4
5
6
7

617. 合并二叉树

力扣传送门

思路：递归，DFS遍历
如果两棵树在同一位置遍历到的节点都不为空，则将两节点的值相加并赋给新节点；
当某棵树的节点为空时，直接将另一棵树的节点返回，合并到新节点下，即便另一棵树下的节点是一颗子树，我们也不用再去遍历了。(这个过程其实也是建树的过程)

 public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
     if (root1 == null) return root2;
     if (root2 == null) return root1;
     TreeNode root = new TreeNode();
     root.val = root1.val+root2.val;
     root.left = mergeTrees(root1.left,root2.left);
     root.right = mergeTrees(root1.right,root2.right);
     return root;
 }
 //可不新建节点，将其中一个树作为合并结果。
1
2
3
4
5
6
7
8
9
10

距离问题

671. 二叉树中第二小的节点

力扣传送门

思路：递归，DFS遍历
如果先不做这道题，给你一个数组[9,1,4,5,6,7] , 不能用排序，仅遍历数组一次，找出最小值和第二小值。如果你会做，那么该题并不难 (其实两次遍历也行，这也就意味着下面要递归两次，但我们是有思想程序员😂）。本质上也是找‘最小值’，只不过该值需要大于min(最小值)
注：根节点就是min，这点没发现也不影响。详情

    private int min;//最小值
    private int second;//第二小值
    public int findSecondMinimumValue(TreeNode root) {
        if (root == null) return -1;
        min = root.val;
        second = -1;
        dfs(root);
        return second;
    }
    void dfs(TreeNode root){
        if (root == null) return;
        if(root.val > min && (root.val < second || second == -1)) {
            second = root.val;
        }
        dfs(root.left);
        dfs(root.right);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

104. 二叉树的最大深度

力扣传送门

思路1：递归，DFS遍历
遍历过程中，每深入下一层，高度加一，达到叶节点时，即为树最深的地方，此时只需判断那个叶子节点最深，即可获得最大深度

 int max = 0;
 public int maxDepth(TreeNode root) {
     dfs(root,0);
     return max;
 }
 void dfs(TreeNode root,int count) {    
     if(root == null){
         if(count > max) {
             max = count;
         }
         return;
     } 
     count++;
     dfs(root.left,count);
     dfs(root.right,count);
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

简化

 public int maxDepth(TreeNode root) {
     if(root == null) return 0;
     return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
 }
1
2
3
4

思路2：层次遍历(BFS)—需要队列(LinkedList)、迭代
利用每一层的节点val属性来记录层数，只需将每一层节点的val值赋值为上一层的层数加一即可。而最后那个元素就是在最后一层，固只需返回其val值即可

class Solution {
    public int maxDepth(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        if(root == null) return 0;
        root.val = 1;//第一层
        queue.add(root);
        TreeNode node = new TreeNode(0);//临时节点
        while(!queue.isEmpty()) {
            node = queue.poll();//出队
            if (node != null) {
                if(node.left != null) {
                    node.left.val = node.val + 1;
                    queue.add(node.left);//入队
                }
                if(node.right != null) {
                    node.right.val = node.val + 1;
                    queue.add(node.right);//入队
                }
            }
        }
        return node.val;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

543. 二叉树的直径

力扣传送门

思路：递归，DFS遍历
本质上就是求树的最大深度----直径可转换为左右子树的深度之和—拆成两棵树，就是在比较左右子树深度时，判断左右子树深度之和是否可能成为最大值。

注意点：如果该题求的是经过根节点的最大直径，则求根节点左右子树高度之和即可，但该路径不一定穿过根节点，所以在遍历每个节点时，都需要判断该节点左右子树高度之和是否有可能成为最大值。例如[1,2,null,3,4,5,null,6]，最大直径就没有穿过根节点

  private int max = 0;
  public int diameterOfBinaryTree(TreeNode root) {
      dfs(root);
      return max;
  }
  public int dfs(TreeNode root){
      if (root == null) return 0;
      int x = dfs(root.left);
      int y = dfs(root.right);
      if (x + y > max) max = x + y;
      return Math.max(x,y) + 1;
  }
1
2
3
4
5
6
7
8
9
10
11
12

110. 平衡二叉树

力扣传送门

思路：递归，DFS遍历
跟543. 二叉树的直径一样，前者求和，这里求差。
求二叉树高度的时候，对每个节点左右子树高度进行做差比较，在用一个布尔类型来标记高度差是否满足要求。

 private boolean ans = true;
 public boolean isBalanced(TreeNode root) {
     dfs(root);
     return ans;
 }
 public int dfs(TreeNode root){
     if (root == null) return 0;
     int x = dfs(root.left);
     int y = dfs(root.right);
     if(Math.abs(x-y) > 1) ans = false; //高度差大于1，不是平衡树
     return Math.max(x,y)+1;
 }
 //还可以优化...
1
2
3
4
5
6
7
8
9
10
11
12
13

力扣传送门

思路：递归，DFS遍历
递归求深度，跟最大深度差不多

注意点：叶子节点，这点类似题目路径总和，边界判断不能跟求最大深度一样，需要读者仔细品味。例如下面最小深度为3，如果在root == null的时候进行判断，则结果为1

    private int min = Integer.MAX_VALUE;
    public int minDepth(TreeNode root) {
        dfs(root,0);
        return min;
    }
    public void dfs(TreeNode root, int count) {
        if(root == null) return;
        count++;//注意求的是节点个数，不是路径
        //特判
        if(root.left == null && root.right == null) {
        	if(min > count) min = count;
            return;
        }
        dfs(root.left,count);
        dfs(root.right,count);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

112. 路径总和

力扣传送门

思路：递归，DFS遍历
我们可以在遍历节点的时候，将目标值减去当前节点值，当到达叶子节点时，判断最后的值是否为0，为0说明存在，是否存在可用布尔类型来做标记。
你也可以传0进去，遇到节点，就累加节点值，当遍历完一条路径，判断和是否为目标值也可以

注意点：叶子节点，是指没有子节点的节点。决定了递归边界条件，判断存不存在，不是在root==null的时候。例如[1,2] 1 结果是flase

    private boolean res = false;
    public boolean hasPathSum(TreeNode root, int targetSum) {        
        dfs(root,targetSum);
        return res;
    }
    public void dfs(TreeNode root, int num){        
        if(root == null) return;        
        if(root.left == null && root.right == null) {
        	 if(num - root.val == 0) res = true;
             return;
        }
        dfs(root.left,num - root.val);
        dfs(root.right,num - root.val);        
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

404. 左叶子之和

力扣传送门

思路：递归，DFS遍历
首先是叶子节点的判断；其次，我们需要区分左右叶子节点，我们知道，如果某叶子节点的上一次递归函数是dfs(left)，则说明该叶子节点是左叶子节点。那么我们就可以通过传入一个参数，来区分上一次调用的函数是dfs(left) 还是dfs(right)，这里用-1和1来区分，调用dfs(left)就传个-1，调用dfs(right)就传个1；
具体就是每次遍历到叶子节点时，根据传入标识判断是不是左叶子节点，如果是，则进行累加即可。

    int sum = 0;
    public int sumOfLeftLeaves(TreeNode root) {
        dfs(root,1);//初始只要不是-1即可
        return sum;
    }
    //利用标识sign
    public void dfs(TreeNode root, int sign) {
        if(root == null) return;
        if(root.left == null && root.right == null) {
            if(sign == -1) {
                sum += root.val;
            }            
            return;
        }
        dfs(root.left,-1);
        dfs(root.right,1);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

*队列 113. 路径总和 II

力扣传送门

思路：递归，DFS遍历
基本跟路径总和一样，主要问题在于解的保存，因为解的个数不确定。这里考察了树遍历的特点，对于传统的遍历，总是先走左边再返回去走右边。虽然解的个数不确定，但解的顺序是就确定的。因此，遍历当前节点时，添加数据，返回时移除数据(已经走过和判断过了)。这样，返回走时，集合就不会包含旧的数据了。

    private List<List<Integer>> res = new LinkedList<>();
    private LinkedList<Integer> queue = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum);
        return res;
    }

    public void dfs(TreeNode root, int targetSum) {
        if(root == null) return;
        //添加到末尾
        queue.add(root.val); 
        //叶子节点特判
        if(root.left == null && root.right == null) {
            if(targetSum == root.val) {
                //引用问题：new LinkedList<>(queue) 底层是addAll()
                res.add(new LinkedList<>(queue));                                
            }
        }        
        dfs(root.left,targetSum - root.val);
        dfs(root.right,targetSum - root.val);
        //移除末尾
        queue.removeLast();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

437. 路径总和 III

力扣传送门

思路：递归+递归或者层次遍历+递归
穷举法，第一层递归，遍历每个节点，第二层递归，把每个节点作为路径的第一个节点，进行递归求和。

    //递归加递归
    private int ans = 0;  
    public int pathSum(TreeNode root, int targetSum) {
        nodeDFS(root,targetSum);
        return ans;
    }
    //递归遍历每个节点
    public void nodeDFS(TreeNode root,int targetSum){
        if(root == null) return;
        //以每个节点作为出发节点
        dfs(root,targetSum);
        nodeDFS(root.left,targetSum);
        nodeDFS(root.right,targetSum);
    }
    //以每个节点作为当前路径的第一个节点
    public void  dfs(TreeNode root,int targetSum) {
       if (root == null) return;
       if (root.val == targetSum) {
           ans++;
       }
       dfs(root.left,targetSum - root.val);
       dfs(root.right,targetSum - root.val);
    }    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

572. 另一棵树的子树

力扣传送门

思路：递归+递归或者层次遍历+递归
非常类似路径总和III，遍历所有子树，即把root的每个节点当作一颗子树的根节点，每一颗子树都和subRoot进行比较。

    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (s == null) return false;
        // 比较、失败则下一棵子树
        return dfs(s,t) || isSubtree(s.left,t) || isSubtree(s.right,t);
    }
    //比较
    boolean dfs(TreeNode s, TreeNode t) {
		if(s == null && t == null) return true;  //边界
        if(s == null || t == null) return false; //仅有一颗
        if (s.val != t.val) return false;  //值不相等
        return dfs(s.left,t.left) && dfs(s.right,t.right);
    }
1
2
3
4
5
6
7
8
9
10
11
12

101. 对称二叉树

力扣传送门

思路：递归，DFS遍历
就是将二叉树分成左右两颗子树，然后同时递归，只是这里递归方向相反，
对于左子树的递归顺序，先左后右，即dfs(left) dfs(right)
对于右子树的递归顺序，先右后左，即dfs(right) dfs(left)
这样就能实现在对称位置的比较，由于我们需要做到一次递归遍历两颗树, 所以递归函数传入参数时，需要传入两个。

    public boolean isSymmetric(TreeNode root) {
        return dfs(root.left,root.right);
    }   
    boolean dfs(TreeNode lRoot, TreeNode rRoot) {
    	//是不是很熟悉。。。上一题
        if(lRoot == null && rRoot == null) return true;//边界
        if(lRoot == null || rRoot == null) return false;//仅有一颗有
        if(lRoot.val != rRoot.val) return false;//值不相等
        //两棵树的递归方向相反，因此能实现两棵树遍历到的节点位置都是对称的
        return dfs(lRoot.left,rRoot.right) && dfs(lRoot.right,rRoot.left);        
    }
1
2
3
4
5
6
7
8
9
10
11