求所有根节点到叶子节点的二叉树路径

心已赠人 2023-06-22 03:28 3阅读 0赞

给一棵二叉树，返回所有从根节点到叶子节点的路径，用list存储

例如，下面的二叉树：

>     1
>      /   \
>     2     3
>      \
>       5

路径：

>     ["1->2->5", "1->3"]

思路：这道题我想多了，我用的非递归双栈模拟实现的，其实根本用不着，递归实现就行。

递归版：

public List<String> binaryTreePaths(TreeNode root) {
        List<String> answer = new ArrayList<String>();
        if (root != null) searchBT(root, "", answer);
        return answer;
    }
    private void searchBT(TreeNode root, String path, List<String> answer) {
        if (root.left == null && root.right == null) answer.add(path + root.val);
        if (root.left != null) searchBT(root.left, path + root.val + "->", answer);
        if (root.right != null) searchBT(root.right, path + root.val + "->", answer);
    }

非递归：

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
    	public List<String> binaryTreePaths(TreeNode root) {
    		LinkedList<TreeNode> is = new LinkedList<TreeNode>();// 记录元素
    		LinkedList<Character> cs = new LinkedList<Character>();// 记录 L or R
    		List<String> res = new ArrayList<String>();
    		TreeNode n = root;
    		while (n != null || is.size() > 0) {
    			while (n != null) {
    				is.addLast(n);
    				cs.addLast('L');
    				n = n.left;
    			}
    			TreeNode t = is.getLast();
    			char type = cs.getLast();
    			if (type == 'L') {
    				cs.removeLast();
    				cs.add('R');
    				n = t.right;
    			} else {
    				if (t.left == null && t.right == null) {
    					StringBuilder sb = new StringBuilder();
    					for (int i = 0; i < is.size() - 1; i++) {
    						sb.append(is.get(i).val + "->");
    					}
    					sb.append(is.get(is.size() - 1).val);
    					res.add(sb.toString());
    				}
    				is.removeLast();
    				cs.removeLast();
    				n = null;
    			}
    		}
    		return res;
    	}
    }

完整代码（递归版）：

import javafx.scene.Node;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /**
     * @author rocling
     */
    public class RecursiveOrNotRecursiveTraversal {
        private static TreeNode root = new TreeNode();
    
        static {
            root.setId(1);
            root.setVal("一");
    
            TreeNode left1 = new TreeNode();
            left1.setId(2);
            left1.setVal("二");
    
            TreeNode right1 = new TreeNode();
            right1.setId(3);
            right1.setVal("三");
    
            TreeNode left2right = new TreeNode();
            left2right.setId(5);
            left2right.setVal("五");
    
            root.setLeft(left1);
            root.setRight(right1);
            left1.setRight(left2right);
        }
    
    
        public static List<String> binaryTreePaths(TreeNode root) {
            List<String> answer = new ArrayList<String>();
            if (root != null) {
                searchBT(root, "", answer);
            }
            return answer;
        }
    
        private static void searchBT(TreeNode root, String path, List<String> answer) {
            //叶子节点
            if (root.left == null && root.right == null) {
                answer.add(path + root.val);
            }
            //左子树
            if (root.left != null) {
                searchBT(root.left, path + root.val + "->", answer);
            }
            //右子树
            if (root.right != null) {
                searchBT(root.right, path + root.val + "->", answer);
            }
        }
    
        public static void main(String[] args) {
            System.out.println(root);
            System.out.println(binaryTreePaths(root));
        }
    }

结果：

> \[一->二->五, 一->三\]