二叉树DFS和BFS遍历

旧城等待， 2023-07-16 11:57 8阅读 0赞

[https://blog.csdn.net/Gene1994/article/details/85097507][https_blog.csdn.net_Gene1994_article_details_85097507]

public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
    }

BFS广度优先遍历：

//使用Queue实现BFS
    public void BFSWithQueue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null)
            queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode treeNode = queue.poll();
     
            //在这里处理遍历到的TreeNode节点
     
            if (treeNode.left != null)
                queue.add(treeNode.left);
            if (treeNode.right != null)
                queue.add(treeNode.right);
        }
    }

DFS：深度优先遍历  采用 递归栈 或者 栈

递归栈

//DFS递归实现
    public void DFSWithRecursion(TreeNode root) {
        if (root == null)
            return;
     
        //在这里处理遍历到的TreeNode节点
            
        if (root.left != null)
            DFSWithRecursion(root.left);
        if (root.right != null)
            DFSWithRecursion(root.right);
    }

栈：这里需要注意 根左右 - > 根右左

//DFS的迭代实现版本（Stack）
    public void DFSWithStack(TreeNode root) {
         if (root == null)
             return;
         Stack<TreeNode> stack = new Stack<>();
         stack.push(root);
     
         while (!stack.isEmpty()) {
             TreeNode treeNode = stack.pop();
     
             //在这里处理遍历到的TreeNode
                 
             if (treeNode.right != null)
                 stack.push(treeNode.right);
     
             if (treeNode.left != null)
                 stack.push(treeNode.left);
         }
    }

[https_blog.csdn.net_Gene1994_article_details_85097507]: https://blog.csdn.net/Gene1994/article/details/85097507