二叉树的中序遍历(递归和非递归方法)（中等题）

给定一个二叉树，返回它的中序 遍历。

示例:

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

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

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

递归方法

private class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
 
 private List<Integer> list=new ArrayList<>();
 public List<Integer> inorderTraversal(TreeNode root) {
     if(null!=root){
         inorderTraversal(root.left);
         list.add(root.val);
         inorderTraversal(root.right);
     }
     return list;
 }

非递归方法，使用栈，先把左子树上的每个节点加入
出栈时遍历，如果有右子树，再把右子树加入栈中，如果右子树有左子树，继续添加左子树，
直至遍历完成。

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list=new ArrayList<>();
    ArrayDeque<TreeNode> stack=new ArrayDeque<>();
    if(null!=root){
        stack.push(root);
    }else{//如果树为空，直接跳出
        return list;
    }

    TreeNode node=root;
    while(null!=node.left){//将左子树上的节点都加入栈
        stack.push(node.left);
        node=node.left;
    }

    while(!stack.isEmpty()){//栈不为空，遍历栈的节点的值，然后如果有右子树，则将右子树的左子树连续入栈，直至没有左子树入栈
       TreeNode node1=stack.pop();
       list.add(node1.val);

       if(null!=node1.right){//右子树不为空
           stack.push(node1.right);//将右子树入栈
           node1=node1.right;//切换到右子树
           while(node1.left!=null){//继续加入右子树的左子树
               stack.push(node1.left);
               node1=node1.left;
           }
       }
    }
    return list;
}

评论区大佬的简洁写法

class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;
            while (cur != null || !stack.isEmpty()) {
                if (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                } else {
                    cur = stack.pop();
                    list.add(cur.val);
                    cur = cur.right;
                }
            }
            return list;
        }
    }

赏

谢谢你请我吃糖果

微信