二叉树的中序遍历

思路

和二叉树的前序遍历十分相似,只是输出的位置不同

二叉树的前序遍历

利用栈的特性存储遍历过的节，先遍历左子树（左子树入栈），当左子树为空时，输出，遍历右子树

1. 遍历左子树
2. 入栈
3. 判断左子树是否为空
   3.1 非空: (1)
   3.2 空值: 出栈，输出，遍历右子树,(1)

整体操作流程

整体动图

详情

遍历左子树

左子树为空出栈，并输出

遍历右子树

完成输出

相关代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        result.addAll(noRecursive(root));
        return result;
        
    }
    
    // 非递归 左根右
    public List<Integer> noRecursive(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while(root!=null||!stack.isEmpty()){
           while(root!=null){
               stack.push(root);
               root = root.left;
           }
            if(!stack.isEmpty()){
                root = stack.pop();
                result.add(root.val);
                root = root.right;
            }
        }
        return result;
    }
    
    // 递归
    public List<Integer> recursive(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if(root==null){
            return result;
        }
        result.addAll(recursive(root.left));
        result.add(root.val);
        result.addAll(recursive(root.right));
        return result;
    }
}