从零学算法94

94.给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]

• 树的中序遍历是是访问树的 左节点 -> 根节点 -> 右节点 这样的顺序，同时，对于每个左节点和右节点，也是遵从同样的访问顺序，你会发现这就是天然的递归，递归的最小基本单元就是 {处理左节点；处理根节点；处理右节点}

•   class Solution {
        List<Integer> list = new ArrayList<>();
        public List<Integer> inorderTraversal(TreeNode root) {
            dfs(root);
            return list;
        }
        public void dfs(TreeNode root){
        	// 如果遍历到 null 就往上返回
            if(root == null)return;
            // 我们要先得到最左节点，所以先处理左节点
            // 处理方式就是一直按照左根右的顺序遍历
            dfs(root.left);
            // 到最左节点后再执行 dfs(root.left) 就会被 return
            // 继续执行，此时的 root 就是最左节点，所以添加到 list
            // 并且其实看下图，对于最左节点 2 来说，它也是一棵树的根节点
            // 也就是说我们这里就是符合
            list.add(root.val);
            // 右节点也是同样的处理方式，让他左根右不断遍历访问
            dfs(root.right);
        }
    }
    		      1                        1    						
    		     /	\  					  /	\
    		 	2    3				     2   3
    		   / \					    / \
    		null  4                  null null
      
  

• 上面的递归隐式地维护了一个栈，我们用迭代的方式显式地表示一遍。

• 首先是 dfs(root.left)，它的作用是不断往左边找节点，找到最左的，找到后往上回溯的时候，是先处理最近递归到的，这就是栈的先进先出的特点，所以它就等价于不断把左节点入栈

• 然后是左节点遍历到 null 后往上回溯到最左节点，然后 list.add(root.val);，回溯到最左节点，其实不就是弹出栈顶元素 node，然后也是把值添加到 list

• 最后是 dfs(root.right);，就是要用同样的方式处理右节点去了，我们就把用来遍历的 root，更新到 node.right 然后继续按照同样的方式处理

•   public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
        	// 不断把左节点入栈
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            if (!stack.isEmpty()) {
            	// 最左节点出栈取值
                TreeNode node = stack.pop();
                list.add(node.val);
                root = node.right;
            }
        }
        return list;
    }