二叉树遍历非递归方式--前序和后序的统一形式

男娘i 2022-05-24 22:49 52阅读 0赞

网址[https://my.oschina.net/husthang/blog/852982][https_my.oschina.net_husthang_blog_852982] 上写的很详细了，如果想验证代码对不对，可以用它里面给出的leetcode链接测试一下。

### DFS非递归实现 ###

#### 前序和后序遍历 ####

*  前序遍历和后序遍历归为一类,所用思想基本一模一样:
 *  前序遍历的步骤为
    
     *  对root进行异常处理
     *  将root压入栈
     *  while循环遍历,终止条件为栈为空，所有元素均已处理完
     *  从栈顶取元素读,取并存入结果
     *  将取出元素的右、左节点分别压入栈内，以便下次循环取元素时为本次节点的左,右子节点.
 *  运用辅助栈,保存遍历到的节点(用栈后入先出的特性,控制已经遍历到的节点的访问顺序). 以前序深度优先遍历为例,先访问根节点,然后访问左树,左树全部访问完了,再访问右树
 *  后续遍历思想: 左-右-根;可以视为, 根-右-左,然后结果转置即可. 如前面示意图,根右左,访问顺序则为:`ACFBED`;可以看出,这样访问刚好为后续遍历的转置. 根右左访问与前序(根左右)遍历操作思想一模一样
 *  前序遍历
    
     *  [leetcode|Binary Tree Preorder Traversal二叉树前序遍历][leetcode_Binary Tree Preorder Traversal]
     *  [lintcode|Binary Tree Preorder Traversal二叉树前序遍历][lintcode_Binary Tree Preorder Traversal]

/** * 前序遍历,迭代法 */
        public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> result = new ArrayList<>();
            if (root == null) return result;
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            while (!stack.isEmpty()) {
                TreeNode node = stack.pop();
                result.add(node.val);
                if (node.right != null) stack.push(node.right);
                if (node.left != null) stack.push(node.left);
            }
            return result;
        }

*  后序遍历
    
     *  [leetcode|Binary Tree Postorder Traversal后序遍历][leetcode_Binary Tree Postorder Traversal]

public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> result = new ArrayList<>();
            if(root == null) return result;
            Deque<TreeNode> stack=new ArrayDeque<>();
            stack.push(root);
            while(!stack.isEmpty()){
                TreeNode node=stack.pop();
                result.add(node.val);
                if(node.left!=null) stack.push(node.left);
                if(node.right!=null) stack.push(node.right);
            }
            Collections.reverse(result);
            return result;
        }

#### 中序遍历 ####

*  中序遍历思路: 中序遍历迭代法思路不同于前序和后序.
    
    1.  首先针对对当前节点,一直对其左子树迭代并将非空节点入栈
    2.  节点指针迭代为空(到树底了)后不再入栈,然后取栈顶元素,存结果;
    3.  将当前指针用出栈的节点的右子节点替代,然后回到第一步继续迭代,直到当前节点为空且栈为空.
 *  [|leetcodeBinary Tree Inorder Traversal中序遍历][leetcodeBinary Tree Inorder Traversal]

public List<Integer> inorderTraversal(TreeNode root){ List<Integer> result = new ArrayList<>(); if(root==null) return result; Deque<TreeNode> stack = new ArrayDeque<>(); while (root!=null||!stack.isEmpty()){ while(root!=null){ stack.push(root); root=root.left; } TreeNode node=stack.pop(); result.add(node.val); root=node.right; } return result; }

[https_my.oschina.net_husthang_blog_852982]: https://my.oschina.net/husthang/blog/852982
[leetcode_Binary Tree Preorder Traversal]: https://leetcode.com/problems/binary-tree-preorder-traversal/
[lintcode_Binary Tree Preorder Traversal]: http://www.lintcode.com/en/problem/binary-tree-preorder-traversal/
[leetcode_Binary Tree Postorder Traversal]: https://leetcode.com/problems/binary-tree-postorder-traversal/
[leetcodeBinary Tree Inorder Traversal]: https://leetcode.com/problems/binary-tree-inorder-traversal/