面试题_DFs(深度度优先算法)

桃扇骨 2022-05-29 09:58 177阅读 0赞

按照图例实现算法；  
![这里写图片描述][Image 1]  
分析题得到：明显是深度度优先算法（DFS算法）/先序遍历；  
**实现方式一：利用栈的方式先进后出**  
**实现方式二：利用递归**  
**创建节点类**

/** * 创建数类 * @author cc_小白成长 * */
    class TreeNode{
        public Integer value;
        public TreeNode leftTree;
        public TreeNode rightTree;
    
        public TreeNode(int value){
            this.value = value;
        } 
    }

**创建二叉树**

/** * 测试数相关方法 * @author cc_小白成长 * */
    public class TestBFs { 
        public static void main(String[] args) {
             TreeNode root = new TreeNode(1);
             root.leftTree = new TreeNode(2);
             root.leftTree.leftTree = new TreeNode(4);
             root.leftTree.rightTree = new TreeNode(5);
             root.rightTree = new TreeNode(3);
             root.rightTree.leftTree  = new TreeNode(6);
             root.rightTree.rightTree = new TreeNode(7);
             TestBFs tb = new TestBFs(); 
             System.out.println("\n深度优先算法--递归");
             tb.DFs_Recursion(root);
             System.out.println("\n深度优先算法--非递归");
             tb.DFs(root);
    
         }
         //方法1放在此处
         //方法2放在此处
        }

**实现方式一：利用栈的方式先进后出**

/** * 深度优先算法，采用非递归方式 利用栈的特性先进后出 * @param root 根节点 */
        public void DFs(TreeNode root) {
            // 判断根节点是否为空
            if (root == null) return; //返回
            //栈 利用栈的特性先进后出
            Stack<TreeNode> list = new Stack<TreeNode>();  
            //把根节点添加到链表中
            list.add(root); 
            TreeNode tr1  ;
            while(!list.isEmpty()){ 
                tr1 = list.pop();// 出栈
                System.out.print(tr1.value+"\t");
                if (tr1.rightTree != null ) { 
                    list.push(tr1.rightTree ); // 重点 先进栈
                }       
                if (tr1.leftTree != null ) { 
                    list.push(tr1.leftTree ); //重点 后进栈
                }
            }        
        }

**实现方式二：利用递归**

/** * 深度优先算法，递归方式 * @param root 根节点 */
        public void DFs_Recursion(TreeNode root) {
            // 判断根节点是否为空
            if (root == null) {
                return; //返回
            }
            System.out.print(root.value+"\t"); // 输出当前值
            if(root.leftTree != null){ // 判断左节点是否为空
                DFs_Recursion(root.leftTree); // 不为空，递归调用
            }
            if(root.rightTree != null) { // 判断右节点是否为空
                DFs_Recursion(root.rightTree); // 不为空，递归调用
            }
        }

测试结果  
![这里写图片描述][Image 1]

关键点：深度优先非递归方法利用栈的特性，***先进后出***

[Image 1]: