LeetCode 二叉树 中序遍历

递归方法

/**
 * 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> a =new ArrayList<Integer>();
        if(root == null)
        {
            return a;
        }
        inorder(root, a);
        return a ;
    }
    public void inorder(TreeNode root, List<Integer> a)
    {
        if(root != null)
        {
            if(root.left != null)
            inorder(root.left, a);

            a.add(new Integer(root.val));
            
            if(root.right != null)
            inorder(root.right, a);}
    }
}

栈的解法：

注意这里的栈里，存放的是 TreeNode, 而不是val,因为 从栈顶弹出来的时候，要找栈顶的节点的孩子，所以不能只存val

 

 public List<Integer> inorderTraversal(TreeNode root) {
        //利用栈算法
        //
        List<Integer> a = new ArrayList<>();
        Stack<TreeNode> b = new Stack<>();
        if(root == null)
        {
            return a ;
        }
        while( root != null|| !b.empty())
        {
            while(root != null)
            {
                b.push(root);
                root = root.left;
            }
            root = b.pop();
            a.add(root.val);
            root = root.right;
                                                                      
        }
        return a;}