94. Binary Tree Inorder Traversal（非递归实现二叉树的中序遍历）

太过爱你忘了你带给我的痛 2022-01-10 04:21 157阅读 0赞

Given a binary tree, return the *inorder* traversal of its nodes' values.

Example:

Input: [1,null,2,3]
       1
        \
         2
        /
       3
    
    Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?

方法一：递归

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public void preorderTraversal(TreeNode root) {
            if(root==null) return ;
            preorderTraversal(root.left);
            System.out.print(root.val+' ');
            preorderTraversal(root.right);
        }
    }

方法二：迭代

中序遍历第左右根，所以设计程序时首先要考虑的是找到最左边的叶子结点。找到之后弹出还要考虑这个结点有没有右孩子。

/**
     * 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) {
            Stack<TreeNode> stack=new Stack<TreeNode>();
            List<Integer> list=new ArrayList<Integer>();
            while (root!=null||!stack.isEmpty()){
                while (root!=null){
                    stack.add(root);
                    root=root.left;
                }
                TreeNode treeNode=stack.pop();
                list.add(treeNode.val);
                root=treeNode.right;  //root是判断条件。每次弹出的结点都要检查是否还有右孩子。有就加入，没有就弹出。
            }
            return list;
        }
    }

转载于:https://www.cnblogs.com/shaer/p/10670452.html