binary-tree-inorder-traversal

ゞ浴缸里的玫瑰 2021-11-09 08:36 152阅读 0赞

/\*\*  
\*  
\* @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][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);
    		}
    	}
    }

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

[https_blog.csdn.net_wang454592297_article_details_79472938]: https://blog.csdn.net/wang454592297/article/details/79472938