二叉树和递归

二叉树天然的递归结构

image-20191030011100767

满二叉树

二叉树的前序遍历 递归实现

1void preOrder(TreeNode node){
2  if(node==null){
3    return;  // 递归终止条件
4  }
5   System.out.print(node.val);
6   preOrder(node.left);    // 递归过程
7   preOrder(node.right);
8}

二叉树的定义：空是一棵二叉树

二叉树总是否包含某个key

 1boolean contain(TreeNode node, Key key){
 2  if(node == null){
 3    return false;
 4  }
 5  if(key == node.key){
 6    return true;
 7  }
 8  if(contain(node.left,key)|| contain(node.right, key)){
 9    return true;
10  }
11  return false;
12}

 1// c++ 释放二叉树的内存
 2void destory(TreeNode node){
 3  if(node == null){
 4    return;
 5  }
 6  destory(node.left);
 7  destory(node.right);
 8  delete node;
 9  count--
10}

LeetCode 104： Maximum Depth of Binary Tree

求一棵二叉树的最高深度，从根节点到叶子节点的最长路径长度

递归实现
1public static int maxDepth(TreeNode root){
2  if(root == NULL){
3    return 0;
4  }
5  return Math.max(maxDepth(root.left), maxDepth(root.right))+1;
6}
非递归实现
 1class Solution {
 2  public int maxDepth(TreeNode root) {
 3    Queue<Pair<TreeNode, Integer>> stack = new LinkedList<>();
 4    if (root != null) {
 5      stack.add(new Pair(root, 1));
 6    }
 7
 8    int depth = 0;
 9    while (!stack.isEmpty()) {
10      Pair<TreeNode, Integer> current = stack.poll();
11      root = current.getKey();
12      int current_depth = current.getValue();
13      if (root != null) {
14        depth = Math.max(depth, current_depth);
15        stack.add(new Pair(root.left, current_depth + 1));
16        stack.add(new Pair(root.right, current_depth + 1));
17      }
18    }
19    return depth;
20  }
21};

复习二叉树相关的所有操作

LeetCode 111：Minimum Depth of Binary Tree

求一棵二叉树的最低深度，从根节点到叶子节点的最短路径长度

 1class Solution {
 2  public int minDepth(TreeNode root) {
 3    if (root == null) {
 4      return 0;
 5    }
 6    
 7    if ((root.left == null) && (root.right == null)) {
 8      return 1;
 9    }
10
11    int min_depth = Integer.MAX_VALUE;
12    if (root.left != null) {
13      min_depth = Math.min(minDepth(root.left), min_depth);
14    }
15    if (root.right != null) {
16      min_depth = Math.min(minDepth(root.right), min_depth);
17    }
18
19    return min_depth + 1;
20  }
21}

一个简单的二叉树问题引发的血案

226： Invert Binary Tree

反转一棵二叉树

Max Howell 因为不会做这道题目而被Google拒绝

Google：90%of our engineer use the software you wrote(Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

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

100: Same Tree

给出两棵二叉树，判断这两棵二叉树是否完全一样

1  public boolean isSameTree(TreeNode p, TreeNode q) {
2    // p and q are both null
3    if (p == null && q == null) return true;
4    // one of p and q is null
5    if (q == null || p == null) return false;
6    if (p.val != q.val) return false;
7    return isSameTree(p.right, q.right) &&
8            isSameTree(p.left, q.left);
9  }

101: Sysmmetric Tree

给出一棵二叉树，判断其是否是左右对称的

 1public boolean isSymmetric(TreeNode root) {
 2    return isMirror(root, root);
 3}
 4
 5public boolean isMirror(TreeNode t1, TreeNode t2) {
 6    if (t1 == null && t2 == null) return true;
 7    if (t1 == null || t2 == null) return false;
 8    return (t1.val == t2.val)
 9        && isMirror(t1.right, t2.left)
10        && isMirror(t1.left, t2.right);
11}

222: Count Complete Tree Node

给定一个棵完全二叉树，求完全二叉树节点的个数

完全二叉树: 除了最后一层，所有层的节点数达到最大，与此同时，最后一层的所有节点都在最左侧。 堆使用完全二叉树。

满二叉树： 所有层的节点数达到最大。

 1    public int countNodes(TreeNode root) {
 2        if(root == null){
 3           return 0;
 4        } 
 5        int left = countLevel(root.left);
 6        int right = countLevel(root.right);
 7        if(left == right){
 8            return countNodes(root.right) + (1<<left);
 9        }else{
10            return countNodes(root.left) + (1<<right);
11        }
12    }
13    private int countLevel(TreeNode root){
14        int level = 0;
15        while(root != null){
16            level++;
17            root = root.left;
18        }
19        return level;
20    }

110 : Balanced Binary Tree

判断一棵树是否为平衡二叉树

平衡二叉树： 每一个节点的左右子树的高度差不超过1

 1public boolean isBalanced(TreeNode root) {
 2    //它是一棵空树
 3    if (root == null) {
 4        return true;
 5    }
 6    //它的左右两个子树的高度差的绝对值不超过1
 7    int leftDepth = getTreeDepth(root.left);
 8    int rightDepth = getTreeDepth(root.right);
 9    if (Math.abs(leftDepth - rightDepth) > 1) {
10        return false;
11    }
12    //左右两个子树都是一棵平衡二叉树
13    return isBalanced(root.left) && isBalanced(root.right);
14
15}
16
17private int getTreeDepth(TreeNode root) {
18    if (root == null) {
19        return 0;
20    }
21    int leftDepth = getTreeDepth(root.left);
22    int rightDepth = getTreeDepth(root.right);
23    return Math.max(leftDepth, rightDepth) + 1;
24}

注意递归的终止条件

112： Path sum

给出一棵二叉树以及一个数字sum, 判断这棵二叉树上是否存在一条从根到叶子的路径。其路径上所有节点和为sum。

易错情况

image-20191031011425387 
 1public static boolean hasPathSum(TreeNode root, int sum){
 2  if( root == null){  // 递归终止条件有问题
 3		return sum == 0;
 4  }
 5  if(hasPathSum(root.left, sum -root.val)){
 6    return true;
 7  }
 8   if(hasPathSum(root.right, sum -root.val)){
 9    return true;
10  }
11  return false;
12}

 1public static boolean hasPathSum(TreeNode root, int sum){
 2  if(root == null){
 3    return false;
 4  }
 5  if( root.left == null && root.right = null){  // 递归终止条件有问题
 6		return sum == root.val;
 7  }
 8  if(hasPathSum(root.left, sum -root.val)){
 9    return true;
10  }
11   if(hasPathSum(root.right, sum -root.val)){
12    return true;
13  }
14  return false;
15  // return hasPathSum(root.left, sum -root.val)||hasPathSum(root.right, sum -root.val);
16}

404：Sum of Left Leaves

求出一棵二叉树所有左叶子的和

1public int sumOfLeftLeaves(TreeNode root) {
2    if (root == null) return 0;
3    if (root.left == null) return  sumOfLeftLeaves(root.right); //如果左子树为空，那么只需返回右子树的左叶子和
4    if (root.left.left == null && root.left.right == null) // 如果左子树为叶子节点，那么需返回右子树的左叶子和 + 左孩子的值
5        return sumOfLeftLeaves(root.right) + root.left.val;
6    return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right); // 其他情况需返回左右子树的左叶子和之和
7}

257: Binary Tree Path

给定一棵二叉树，返回所有表示从根节点到叶子节点路径的字符串

 1    public List<String> binaryTreePaths(TreeNode root) {
 2        List<String> list = new ArrayList<>();
 3        if(root == null){
 4            return list;
 5        }
 6        if(root.left == null && root.right == null){
 7           list.add(""+root.val);
 8        }
 9        List<String> left = binaryTreePaths(root.left);
10        for(String str: left){
11            list.add(""+root.val+"->"+str);
12        }
13        List<String> right = binaryTreePaths(root.right);
14         for(String str: right){
15             list.add(""+root.val+"->"+str);
16        }
17        return list;
18    }

113：Path Sum II

给定一棵二叉树，返回所有从根节点到叶子节点的路径，其和为sum

对于右侧二叉树，sum = 22，结果为[[5,4,11,2],[5,4,8,5]]

129：Sum root to Leaf Numbers

给定一棵二叉树，每个节点只包含数字0-9，从根节点到叶子节点的每条路径可以表示成一个数，求这些数的和。

更复杂的递归逻辑

437： Path Sum II

给出一棵二叉树以及一个数字sum，判断在这棵二叉树上存在多少条路径，其路径上所有节点和为sum。

  • 其中路径不一定哟啊起始于根节点；终止于叶子节点
  • 路径可以从任意节点开始，但是只能是向下走的。