binary-tree-inorder-traversal

/**
*
* @author gentleKay
* Given a binary tree, return the inorder traversal of its nodes’ values.
* For example:
* Given binary tree{1,#,2,3},
1
\
2
/
3
* return[1,3,2].
* Note: Recursive solution is trivial, could you do it iteratively?
* confused what”{1,#,2,3}“means? > read more on how binary tree is serialized on OJ.
* 给定二叉树，返回其节点值的中序遍历。
* 例如：
* 给定二叉树1，，2,3，
* 返回[1,3,2]。
* 注意：递归解决方案很简单，可以迭代吗？
*/

推荐一个博客（关于递归和非递归二叉树的遍历）

https://blog.csdn.net/wang454592297/article/details/79472938

方法一：（非递归进行中序遍历）

import java.util.ArrayList;
import java.util.Stack;
/**
 * 
 * @author gentleKay
 * Given a binary tree, return the inorder traversal of its nodes' values.
 * For example:
 * Given binary tree{1,#,2,3},
   1
    \
     2
    /
   3
 * return[1,3,2].
 * Note: Recursive solution is trivial, could you do it iteratively?
 * confused what"{1,#,2,3}"means? > read more on how binary tree is serialized on OJ.
 * 给定二叉树，返回其节点值的中序遍历。
 * 例如：
 * 给定二叉树1，，2,3，
 * 返回[1,3,2]。
 * 注意：递归解决方案很简单，可以迭代吗？
 */
public class Main21 {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
//        TreeNode root = null;
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(1);
        root.left.right  = new TreeNode(3);
        root.right = new TreeNode(6);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(7);
        root.right.right.right = new TreeNode(8);
        System.out.println(Main21.inorderTraversal(root));
    }
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    public static ArrayList<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        ArrayList<Integer> array = new ArrayList<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            if (!stack.isEmpty()) {
                root = stack.pop();
                array.add(root.val);
                root = root.right;
            }
        }
        return array;
    }
}

方法二：（递归进行中序遍历）

import java.util.ArrayList;
import java.util.Stack;
/**
 * 
 * @author gentleKay
 * Given a binary tree, return the inorder traversal of its nodes' values.
 * For example:
 * Given binary tree{1,#,2,3},
   1
    \
     2
    /
   3
 * return[1,3,2].
 * Note: Recursive solution is trivial, could you do it iteratively?
 * confused what"{1,#,2,3}"means? > read more on how binary tree is serialized on OJ.
 * 给定二叉树，返回其节点值的中序遍历。
 * 例如：
 * 给定二叉树1，，2,3，
 * 返回[1,3,2]。
 * 注意：递归解决方案很简单，可以迭代吗？
 */
public class Main21 {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
//        TreeNode root = null;
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(1);
        root.left.right  = new TreeNode(3);
        root.right = new TreeNode(6);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(7);
        root.right.right.right = new TreeNode(8);
        System.out.println(Main21.inorderTraversal(root));
    }
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    static ArrayList<Integer> array = new ArrayList<>();
    public static ArrayList<Integer> inorderTraversal(TreeNode root) {
        if (root == null) {
            return array;
        }
        ergodic(root);
        return array;
    }
    public static void ergodic(TreeNode root) {
        if (root.left != null) {
            ergodic(root.left);
        }
        array.add(root.val);
        if (root.right != null) {
            ergodic(root.right);
        }
    }
}

转载于//www.cnblogs.com/strive-19970713/p/11271596.html