题目

(https://leetcode.com/problems/binary-tree-inorder-traversal/)
给定一个二叉树，返回它的中序 遍历。

示例:

输入: [1,null,2,3]
1

2
/
3

输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析

image.png

参考一篇感觉写的比较好的
(https://www.cnblogs.com/llguanli/p/7363657.html)

代码

递归代码
class Solution {

  class Solution {
    List<Integer> results= new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(null!=root){
            //遍历左子树
            inorderTraversal(root.left);
            results.add(root.val);
            //遍历右子树
            inorderTraversal(root.right);
        }
        return results;
    }
}


非递归
class Solution {

    LinkedList<TreeNode> stack = new LinkedList<>();  
    List<Integer> results = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        
        LinkedList<TreeNode> stack = new LinkedList<>();  
        TreeNode pNode = root;  
        while (pNode != null || !stack.isEmpty()) {  
            if (pNode != null) {  
                stack.push(pNode);  
                pNode = pNode.left;  
            } else { //pNode == null && !stack.isEmpty()   
                TreeNode node = stack.pop();  
                results.add(node.val); 
                pNode = node.right;  
            }  
        }  
        return results;
    }
}

结果

递归结果

image.png

非递归结果

zuo