算法精选题总结之二叉树类

1.二叉树的中序遍历

中序遍历的迭代方法
中序遍历的递归方法

2.二叉树前序遍历
3.二叉树后续遍历
4.二叉树的最近公共祖先
5.二叉树的层次遍历
6.二叉树的最大深度
7.二叉树的最小深度

二叉树的前序、中序、后续遍历都是以root节点来看的，如果root节点比它的左右节点先遍历，就是前序遍历。如果root节点在左节点之后遍历，在右节点之前遍历，就是中序遍历。如果root节点在左右节点之后遍历，就是后序遍历。

1.二叉树的中序遍历

给定一个二叉树，返回它的中序 遍历。递归与迭代都可以试试看看，递归代码很简单，但是也不能忘了迭代的方式。中序遍历实际上就是深度遍历的一种，所以使用栈，栈和队列在二叉树中使用非常广泛。下面还会详细地谈到。
中序遍历的迭代方式：

class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;
            while (cur != null || !stack.isEmpty()) {
                if (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                } else {
                    cur = stack.pop();
                    list.add(cur.val);
                    cur = cur.right;
                }
            }
            return list;
        }
}

中序遍历的递归方式：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        return inorder(root, list);
    }

    private List<Integer> inorder(TreeNode root, List<Integer> list) {
        if (root != null) {
            inorder(root.left, list);
            list.add(root.val);
            inorder(root.right, list);
        }
        return list;
    }
}

2.二叉树前序遍历

class Solution {
        public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;
            while (cur != null || !stack.isEmpty()) {
                if (cur != null) {
                    stack.push(cur);
                    list.add(cur.val);
                    cur = cur.left;
                } else {
                    cur = stack.pop();
                    cur = cur.right;
                }
            }
            return list;
        }
}

3.二叉树后续遍历

    List<Integer> postorderTraversal(TreeNode root) {
             List<Integer> list = new LinkedList<>();
             Stack<TreeNode> stack = new Stack<>();

             TreeNode cur = root;
             TreeNode last = null;
             while (cur != null || !stack.isEmpty()) {
                     while (cur != null) {
                             stack.add(cur);
                             cur = cur.left;
                     }

                     cur = stack.peek();
                     if (cur.right == null || cur.right == last) {
                             stack.pop();
                             list.add(cur.val);
                             last = cur;
                             cur = null;
                     } else {
                             cur = cur.right;
                     }
             }
             return list;
     }
}

一定要确定当前节点的左子树和右子树都遍历完了，才能开始读取stack。
if (cur.right == null || cur.right == last) 表示当前右子树为空或者右子树已经被访问过，说明此时直接可以访问栈中的元素了，栈中的元素肯定是左节点或者根节点，但是有前提条件，根节点肯定是最后访问的。

4.二叉树的最近公共祖先

class Solution {
    /**
    方法1： 找出node p和node q的所有路径再比较
    方法2： 递归，查找。（本题采用方法2，时间复杂度o（n））
    **/
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // root为空
        if(root == null || p == null || q == null) {
            return null;
        }
        // 如果p或者q为root（返回条件）
        if(root == p || root == q) {
            return root;
        }
        // 递归左子树，找到左子树中的p或者q
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        // 递归右子树，找到右子树中的p或者q
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 如果左子树找不到任何一个，返回右子树
        if(left == null) {
            return right;
        }
        // 如果右子树也找不到任何一个，返回左子树
        if(right == null) {
            return left;
        }
        // 否则，左右字数都能找到任何一个，说明当前root为祖先节点 
        return root;        
    }
}

5.二叉树的层次遍历

二叉树的层次遍历，就是广度遍历，广度遍历使用队列，深度遍历使用栈。这些都是利用队列和栈的特性来实现的。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null)
            return new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty()){
            int count = queue.size();
            List<Integer> list = new ArrayList<Integer>();
            while(count > 0){
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left != null)
                    queue.add(node.left);
                if(node.right != null)
                    queue.add(node.right);
                count--;
            }
            res.add(list);
        }
        return res;
    }
}

6.二叉树的最大深度

思路很简单，采用广度优先遍历的方法，可以将二叉树的深度确定一下。

class Solution {
public static int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int preCount = 1;
        int pCount = 0;

        int level = 0;

        while (!q.isEmpty()) {
            TreeNode temp = q.poll();
            preCount--;

            if (temp.left != null) {
                q.offer(temp.left);
                pCount++;
            }
            if (temp.right != null) {
                q.offer(temp.right);
                pCount++;
            }

            if (preCount == 0) {
                preCount = pCount;
                pCount = 0;
                // System.out.println();
                level++;
            }
        }
        return level;
    }
}

7.二叉树的最小深度

class Solution {
    public int minDepth(TreeNode root) {
        if(root==null)return 0;
        else if(root.left==null && root.right==null){
            return 1;
        } else if(root.left==null){
            return minDepth(root.right)+1;
        } else if(root.right==null){
            return minDepth(root.left)+1;
        }else{
            int left = minDepth(root.right);
            int right = minDepth(root.left);
            return left > right?right+1:left+1;
        }
    }
}