LeetCode入门指南 之 二叉树

二叉树的遍历

递归：

void traverse (TreeNode root) {

    if (root == null) {

        return null;

    }

    //前序遍历位置

    traverse(root.left);

    //中序遍历位置

    traverse(root.right);

    //后序遍历位置

}

144. 二叉树的前序遍历

前序非递归：

public static List<Integer> preOrder(TreeNode root) {

    if (root == null) {

        return null;

    }

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

    Deque<TreeNode> stack = new LinkedList<>();

    stack.push(root);

    while (!stack.isEmpty()) {

        // 先遍历根结点

        TreeNode node = stack.pop();

        res.add(node.val);

        // 打印顺序为：根 左 右，因此先将右子结点入栈

        if (node.right != null) {

            stack.push(node.right);

        }

        if (node.left != null) {

            stack.push(node.left);

        }

    }

    return res;

}

94. 二叉树的中序遍历

中序非递归：

 public static List<Integer> infixOrder(TreeNode root) {

     if (root == null) {

        return null;

     }

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

     TreeNode temp = root;

     Deque<TreeNode> stack = new LinkedList<>();

     while (temp != null || !stack.isEmpty()) {

         while (temp != null) {

             stack.push(temp); // 加入栈

             temp = temp.left; // 到最左边结点停止

         }

         temp = stack.pop();   // 访问栈顶元素

         res.add(temp.val);

         temp = temp.right;    //下一个遍历的元素是temp的右子树的最左边结点

     }

     return res;

 }

145. 二叉树的后序遍历

后序非递归：

// 后序可参照前序：后序为：左右根，我们只需按照:根右左遍历然后翻转即可

public static List<Integer> postOrder(TreeNode root) {

    if (root == null) {

        return null;

    }

    LinkedList<Integer> res = new LinkedList<>();

    Deque<TreeNode> stack = new LinkedList<>();

    stack.push(root);

    while (!stack.isEmpty()) {

        TreeNode temp = stack.pop();

        // 每次添加到头，最后输出的结果自然为：根右左的逆序

        res.addFirst(temp.val);

        if (temp.left != null) {

            stack.push(temp.left);

        }

        if (temp.right != null) {

            stack.push(temp.right);

        }

    }

    return res;

}

注意 ：如果非递归解法难以理解，可以先按照上面的代码结合案例手推一下。重要的还是要先形成模板并记忆，间隔着多做几次也就慢慢理解了。

102. 二叉树的层序遍历

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode() {}

 *     TreeNode(int val) { this.val = val; }

 *     TreeNode(int val, TreeNode left, TreeNode right) {

 *         this.val = val;

 *         this.left = left;

 *         this.right = right;

 *     }

 * }

 */

class Solution {

    public List<List<Integer>> levelOrder(TreeNode root) {

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

        if (root == null) {

            return res;

        }

		// 创建队列并加入头结点

        Deque<TreeNode> queue = new LinkedList<>();

        queue.offer(root);

        while (!queue.isEmpty()) {

            // 获取当前层的结点个数

            int size = queue.size();

            List<Integer> rowList = new LinkedList<>();

            // 将当前层结点按照先进先出（从左至右）的方式出队，同时将非空子结点加入队尾

            for (int i = 0; i < size; i++) {

                TreeNode node = queue.poll();

                rowList.add(node.val);

                if (node.left != null) {

                    queue.offer(node.left);

                }

                if (node.right != null) {

                    queue.offer(node.right);

                }

            }

            res.add(rowList);

        }

        return res;

    }

}

104. 二叉树的最大深度

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

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

lass Solution {

    /**

     * 定义：

     *      返回以root为根结点的最大深度

     */

    public int maxDepth(TreeNode root) {

        //base case, root为空说明树的高度为0，退出递归

        if (root == null) {

            return 0;

        }

        /**

         *  根据定义，就根节点来说，树的最大深度为：

         *    左右子树的最大深度中的最大值 + 1

         */

        int left = maxDepth(root.left);

        int right = maxDepth(root.right);

        return 1 + Math.max(left, right);

    }

}

• 二叉树相关的很多题目都是由二叉树的三种递归遍历演化而来
• 此题其实就是二叉树的后序遍历演化而来，要知道当前二叉树的最大深度自然要先知道两棵子树的最大深度，因此用后序遍历（自底向上）
• 编写递归程序切记不要用脑袋模拟递归栈，函数定义好后，根据定义编写代码即可

110. 平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

class Solution {

    //先假定是平衡二叉树

    private boolean balance = true;

    public boolean isBalanced(TreeNode root) {

        height(root);

        return balance;

    }

    //后序遍历而来，自底向上获取两棵子树的高度，并检查节点左右子树高度只差是否小于等于1

    private int height(TreeNode root) {

        if (root == null) {

            return 0;

        }

        int left = height(root.left);

        int right = height(root.right);

        if (Math.abs(left - right) > 1) {

            balance = false;

        }

        return Math.max(left, right) + 1;

    }

}

124. 二叉树中的最大路径和

路径 被定义为一条从树中任意节点出发，沿父节点 - 子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode() {}

 *     TreeNode(int val) { this.val = val; }

 *     TreeNode(int val, TreeNode left, TreeNode right) {

 *         this.val = val;

 *         this.left = left;

 *         this.right = right;

 *     }

 * }

 */

class Solution {

    public int maxPathSum(TreeNode root) {

        maxSumToDescendant(root);

        return maxPathSum;

    }

	//先将 树的最大路径和 初始化为最小值

    private int maxPathSum = Integer.MIN_VALUE;

    // 函数定义：当前结点到 子孙（不一定包含叶子结点） 结点的最大路径和（最少为其自身一个结点）

    private int maxSumToDescendant(TreeNode root) {

        if (root == null) {

            return 0;

        }

        // 小于0则认为对最大路径和没有贡献

        int left = Math.max(0, maxSumToDescendant(root.left));

        int right = Math.max(0, maxSumToDescendant(root.right));

        // 自底向上返回的过程中顺带计算 树的最大路径和（当前结点到左边子孙结点的最大路径和 + 当前结点 + 当前结点到右边子孙结点的最大路径和）

        maxPathSum = Math.max(maxPathSum, left + root.val + right);

        return root.val + Math.max(left, right);

    }

}

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

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

思路：后序遍历演变而来，若找到其中一个结点就自底向上返回。若p、q互不为对方子树中的结点，p、q最终会在某个结点相遇，该节点就为最近公共祖先；否则p或q即为最近公共结点。

class Solution {

    //重要已知：p != q

    //     p 和 q 均存在于给定的二叉树中。

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if (root == null || root == p || root == q) {

            return root;

        }

        TreeNode left = lowestCommonAncestor(root.left, p, q);

        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if (left != null && right != null) {

            return root;

        }

        return left != null ? left : right;

    }

}

107. 二叉树的层序遍历 II

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

class Solution {

    public List<List<Integer>> levelOrderBottom(TreeNode root) {

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

        if (root == null) {

            return res;

        }

        Deque<TreeNode> queue = new LinkedList<>();

        queue.offerLast(root);

        while (!queue.isEmpty()) {

            //获取当前层的结点数量

            int size = queue.size();

            //暂存当前层的所有结点

            List<Integer> tempList = new LinkedList<>();

            TreeNode tempNode;

            for (int i = 0; i < size; i++) {

                tempNode = queue.poll();

                tempList.add(tempNode.val);

                if (tempNode.left != null) {

                    queue.offer(tempNode.left);

                }

                if (tempNode.right != null) {

                    queue.offer(tempNode.right);

                }

            }

            //将每一层的结果 逆序 放入最终的list中

            res.addFirst(tempList);

        }

        return res;

    }

}

103. 二叉树的锯齿形层序遍历

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

class Solution {

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {

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

        if (root == null) {

            return res;

        }

        Deque<TreeNode> queue = new LinkedList<>();

        queue.offerLast(root);

        boolean flag = true;

        while(!queue.isEmpty()) {

            //获取当前层的结点数量

            int size = queue.size();

            LinkedList<Integer> tempList = new LinkedList<>();

            TreeNode tempNode;

            for (int i = 0; i < size; i++) {

                tempNode = queue.pollFirst();

                if (flag == true) {

                    //从前往后，顺序存放

                    tempList.addLast(tempNode.val);

                } else {

                    //从前往后，逆序存放

                    tempList.addFirst(tempNode.val);

                }

                if (tempNode.left != null) {

                    queue.offerLast(tempNode.left);

                }

                if (tempNode.right != null) {

                    queue.offerLast(tempNode.right);

                }

            }

            res.add(tempList);

            //每遍历完一层切换flag

            flag = !flag;

        }

        return res;

    }

}

二叉搜索树

98. 验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

• 节点的左子树只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode() {}

 *     TreeNode(int val) { this.val = val; }

 *     TreeNode(int val, TreeNode left, TreeNode right) {

 *         this.val = val;

 *         this.left = left;

 *         this.right = right;

 *     }

 * }

 */

class Solution {

    public boolean isValidBST(TreeNode root) {

        return isValidBST(root, null, null);

    }

    //定义：当前结点为根结点的二叉树是否为二叉搜索树。二叉搜索树的每个结点都有一个上下界（除了根节点）

    private boolean isValidBST(TreeNode node, TreeNode low, TreeNode high) {

        //base case

        if (node == null) {

            return true;

        }

        //base case，当前结点小于等于下界或大于等于上界都不满足二叉搜索树

        if (low != null && node.val <= low.val) return false;

        if (high != null && node.val >= high.val) return false;

        boolean ret = isValidBST(node.left, low, node) && isValidBST(node.right, node, high);

        return ret;

    }

}

推荐题解：验证二叉搜索树（BST：给子树上所有节点都加一个边界）

701. 二叉搜索树中的插入操作

给定二叉搜索树（ BST ）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

注意 ，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

class Solution {

    // 定义：将当前值插入以当前结点为根的二叉搜索树并返回根节点

    public TreeNode insertIntoBST(TreeNode root, int val) {

        if (root == null) {

            return new TreeNode(val);

        }

        // 一定要根据定义来编写递归代码

        if (root.val > val) {

            // val 小于当前结点值则插入左子树

            root.left = insertIntoBST(root.left, val);

        } else {

            root.right = insertIntoBST(root.right, val);

        }

        return root;

    }

}

450. 删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key ，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

1. 首先找到需要删除的节点；
2. 如果找到了，删除它。

说明： 要求算法时间复杂度为 O(h)，h 为树的高度。

class Solution {

    // 定义：删除当前结点为根结点的二叉搜索树中值为 key 的结点

    public TreeNode deleteNode(TreeNode root, int key) {

        // base case

        if (root == null) {

            return root;

        }

        // 切记根据定义编写递归代码

        if (root.val == key) {

            //base case, 删除结点是叶子结点或只是有一个子树的非叶结点

            if (root.left == null) return root.right;

            if (root.right == null) return root.left;

            // 有两个子树的非叶子结点，用右子树的最小结点替换当前结点，然后删除右子树最小结点

            TreeNode node = getMin(root.right);

            root.val = node.val;

            root.right = deleteNode(root.right, node.val);

          // key 大于当前结点值 则根据定义在右子树中删除

        } else if (root.val < key) {

            root.right = deleteNode(root.right, key);

        } else if (root.val > key){

            root.left = deleteNode(root.left, key);

        }

        return root;

    }

    // 获取root为根的子树的最小结点（最左边结点）

    private TreeNode getMin(TreeNode root) {

        while(root.left != null) {

            root = root.left;

        }

        return root;

    }

}