基本知识

新建一个二叉树

使用数组确定一个唯一的二叉树（leetcode）

leetcode是采用了层序遍历的方法用一个一维数组表示了二叉树，表示要点是：

1. 数组第一个元素是根节点
2. 左右子树为空时用null表示
3. null元素的左右子树不显示

依照三个原则，我们来看一下如何还原一个二叉树吧！

{2,null,4,9,8,null,null,4}这个表示一个什么样的二叉树呢？ 数组的第一个元素是根节点 2 左右子树为空时用null表示 2 null 4 null元素的左右子树不显示

                 2
     ----------------
    null                4

---

不显示 不显示 9 8

              --------  -------
              null null null  4

使用节点确定一个唯一的二叉树

public class TreeNode{
    int value;
    TreeNode left;
    TreeNode right;
    /*省略getter和setter方法*/
}

一维数组转TreeNode节点

二叉树遍历

递归法

// 中序遍历递归法
    public List<Integer> inorderTraversalRecursion(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        inorderTraversalRecursion(root, result);
        return result;
    }

    private void inorderTraversalRecursion(TreeNode root, List<Integer> list) {
        if (root==null) {
            // 递归结束
            return;
        }
        inorderTraversalRecursion(root.left, list);
        list.add(root.val);
        inorderTraversalRecursion(root.right, list);
    }

迭代法

// 中序遍历循环迭代法
    public List<Integer> inorderTraversalIteration(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        // 先将所有的左子树压栈
        while (root!=null) {
            stack.push(root);
            root = root.left;
        }
        // 当栈不空时
        while (!stack.isEmpty()) {
            // 弹出最左侧的节点
            TreeNode current = stack.pop();
            result.add(current.val);
            // 准备去处理当前节点的右节点，一样的需要把所有的左节点入栈，走到最左侧
            current = current.right;
            while (current!=null) {
                stack.push(current);
                current = current.left;
            }
        }
        return result;
    }