inOrder 二叉树中序遍历

慢慢练脑子

1. 来源：

题： leetcode

2. 解法：

2.1 递归

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        helper(result, root);
        
        return result;
    }
    
    private void helper(List<Integer> result, TreeNode root) {
        
        if(root == null) {
            return;
        }
        
        helper(result, root.left);
        result.add(root.val);
        helper(result, root.right);
        
    }
}

2.1 非递归

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        
        List<Integer> inOrderList = new ArrayList<>();
        if(root == null) {
            return inOrderList;
        }
        
        Stack<TreeNode> nodeStack = new Stack<>();
        while(root != null) {
            nodeStack.push(root);
            root = root.left;
        }
        
        while(! nodeStack.isEmpty()) {
            TreeNode curNode = nodeStack.peek();
            inOrderList.add(curNode.val);
            
            if(curNode.right != null) {
                curNode = curNode.right;
                while(curNode != null) {
                    
                    nodeStack.push(curNode);
                    curNode = curNode.left;
                    
                }
                
            } else {
                curNode = nodeStack.pop();
                while(!nodeStack.isEmpty()
                     && nodeStack.peek().right == curNode) {
                    curNode = nodeStack.pop();
                }
                
            }
            
        }
        
        return inOrderList;
    }
}